1 #include <darwintest.h>
2 #include <darwintest_utils.h>
3 #include <stdio.h>
4 #include <assert.h>
5 #include <setjmp.h>
6 #include <os/tsd.h>
7
8 #define DEVELOPMENT 1
9 #define DEBUG 0
10 #define XNU_KERNEL_PRIVATE 1
11
12 #define OS_REFCNT_DEBUG 1
13 #define STRESS_TESTS 0
14 #define __zpercpu
15
16 #pragma clang diagnostic ignored "-Watomic-implicit-seq-cst"
17 #pragma clang diagnostic ignored "-Wc++98-compat"
18
19 __abortlike
20 void handle_panic(const char *func, char *str, ...);
21 #define panic(...) handle_panic(__func__, __VA_ARGS__)
22
23 #define ZPERCPU_STRIDE 128
24
25 static inline int
zpercpu_count(void)26 zpercpu_count(void)
27 {
28 static int n;
29 if (__improbable(n == 0)) {
30 n = dt_ncpu();
31 }
32 return n;
33 }
34
35 static inline void
thread_wakeup(void * event)36 thread_wakeup(void *event)
37 {
38 abort();
39 }
40
41 #define zalloc_percpu(zone, flags) \
42 (uint64_t _Atomic *)calloc((size_t)zpercpu_count(), ZPERCPU_STRIDE)
43
44 #define zfree_percpu(zone, ptr) \
45 free(ptr)
46
47 static inline uint64_t _Atomic *
zpercpu_get_cpu(uint64_t _Atomic * ptr,int cpu)48 zpercpu_get_cpu(uint64_t _Atomic *ptr, int cpu)
49 {
50 return (uint64_t _Atomic *)((uintptr_t)ptr + (uintptr_t)cpu * ZPERCPU_STRIDE);
51 }
52
53 #define zpercpu_get(ptr) zpercpu_get_cpu(ptr, 0)
54
55 #define zpercpu_foreach_cpu(cpu) \
56 for (int cpu = 0, __n = zpercpu_count(); cpu < __n; cpu++)
57
58 #define zpercpu_foreach(cpu) \
59 for (int cpu = 0, __n = zpercpu_count(); cpu < __n; cpu++)
60
61 #define cpu_number() (int)_os_cpu_number()
62
63 #include "../libkern/os/refcnt.h"
64 #include "../libkern/os/refcnt.c"
65
66 T_GLOBAL_META(T_META_RUN_CONCURRENTLY(true));
67
68 /* import some of the refcnt internal state for testing */
69 extern bool ref_debug_enable;
70 os_refgrp_decl_extern(global_ref_group);
71
72 T_GLOBAL_META(
73 T_META_NAMESPACE("os_refcnt"),
74 T_META_CHECK_LEAKS(false)
75 );
76
77 T_DECL(os_refcnt, "Basic atomic refcount")
78 {
79 struct os_refcnt rc;
80 os_ref_init(&rc, NULL);
81 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 1, "refcount correctly initialized");
82
83 os_ref_retain(&rc);
84 os_ref_retain(&rc);
85 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 3, "retain increased count");
86
87 os_ref_count_t x = os_ref_release(&rc);
88 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 2, "release decreased count");
89 T_ASSERT_EQ_UINT(x, 2, "release returned correct count");
90
91 os_ref_release_live(&rc);
92 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 1, "release_live decreased count");
93
94 x = os_ref_release(&rc);
95 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 0, "released");
96 T_ASSERT_EQ_UINT(x, 0, "returned released");
97
98 os_ref_init(&rc, NULL);
99 T_ASSERT_TRUE(os_ref_retain_try(&rc), "try retained");
100
101 (void)os_ref_release(&rc);
102 (void)os_ref_release(&rc);
103 T_QUIET; T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 0, "release");
104
105 T_ASSERT_FALSE(os_ref_retain_try(&rc), "try failed");
106 }
107
108 T_DECL(os_pcpu_refcnt, "Basic atomic refcount")
109 {
110 dispatch_queue_t rq = dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0);
111 dispatch_group_t g = dispatch_group_create();
112 os_pcpu_ref_t rc;
113
114 os_pcpu_ref_init(&rc, NULL);
115 T_ASSERT_EQ_UINT(os_pcpu_ref_count(rc), OS_REFCNT_MAX_COUNT,
116 "refcount correctly initialized");
117
118 dispatch_group_async(g, rq, ^{
119 os_pcpu_ref_retain(rc, NULL);
120 });
121 dispatch_group_async(g, rq, ^{
122 T_ASSERT_TRUE(os_pcpu_ref_retain_try(rc, NULL), "try succeeded");
123 });
124 dispatch_group_wait(g, DISPATCH_TIME_FOREVER);
125
126 T_ASSERT_EQ_UINT(os_pcpu_ref_count(rc), OS_REFCNT_MAX_COUNT,
127 "retain increased count");
128
129 T_ASSERT_EQ_UINT(os_pcpu_ref_kill(rc, NULL), 2,
130 "kill decreased count");
131 T_ASSERT_EQ_UINT(os_pcpu_ref_count(rc), 2,
132 "kill decreased count");
133
134 T_ASSERT_FALSE(os_pcpu_ref_retain_try(rc, NULL), "try failed");
135
136 os_pcpu_ref_release_live(rc, NULL);
137 T_ASSERT_EQ_UINT(os_pcpu_ref_count(rc), 1, "release_live decreased count");
138
139 T_ASSERT_EQ_UINT(os_pcpu_ref_release(rc, NULL), 0, "returned released");
140 T_ASSERT_EQ_UINT(os_pcpu_ref_count(rc), 0, "released");
141
142 os_pcpu_ref_destroy(&rc, NULL);
143 }
144
145 T_DECL(refcnt_raw, "Raw refcount")
146 {
147 os_ref_atomic_t rc;
148 os_ref_init_raw(&rc, NULL);
149 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 1, "refcount correctly initialized");
150
151 os_ref_retain_raw(&rc, NULL);
152 os_ref_retain_raw(&rc, NULL);
153 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 3, "retain increased count");
154
155 os_ref_count_t x = os_ref_release_raw(&rc, NULL);
156 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 2, "release decreased count");
157 T_ASSERT_EQ_UINT(x, 2, "release returned correct count");
158
159 os_ref_release_live_raw(&rc, NULL);
160 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 1, "release_live decreased count");
161
162 x = os_ref_release_raw(&rc, NULL);
163 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 0, "released");
164 T_ASSERT_EQ_UINT(x, 0, "returned released");
165
166 os_ref_init_raw(&rc, NULL);
167 T_ASSERT_TRUE(os_ref_retain_try_raw(&rc, NULL), "try retained");
168
169 (void)os_ref_release_raw(&rc, NULL);
170 (void)os_ref_release_raw(&rc, NULL);
171 T_QUIET; T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 0, "release");
172
173 T_ASSERT_FALSE(os_ref_retain_try_raw(&rc, NULL), "try failed");
174 }
175
176 T_DECL(refcnt_locked, "Locked refcount")
177 {
178 struct os_refcnt rc;
179 os_ref_init(&rc, NULL);
180
181 os_ref_retain_locked(&rc);
182 os_ref_retain_locked(&rc);
183 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 3, "retain increased count");
184
185 os_ref_count_t x = os_ref_release_locked(&rc);
186 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 2, "release decreased count");
187 T_ASSERT_EQ_UINT(x, 2, "release returned correct count");
188
189 (void)os_ref_release_locked(&rc);
190 x = os_ref_release_locked(&rc);
191 T_ASSERT_EQ_UINT(os_ref_get_count(&rc), 0, "released");
192 T_ASSERT_EQ_UINT(x, 0, "returned released");
193 }
194
195 T_DECL(refcnt_raw_locked, "Locked raw refcount")
196 {
197 os_ref_atomic_t rc;
198 os_ref_init_raw(&rc, NULL);
199
200 os_ref_retain_locked_raw(&rc, NULL);
201 os_ref_retain_locked_raw(&rc, NULL);
202 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 3, "retain increased count");
203
204 os_ref_count_t x = os_ref_release_locked_raw(&rc, NULL);
205 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 2, "release decreased count");
206 T_ASSERT_EQ_UINT(x, 2, "release returned correct count");
207
208 (void)os_ref_release_locked_raw(&rc, NULL);
209 x = os_ref_release_locked_raw(&rc, NULL);
210 T_ASSERT_EQ_UINT(os_ref_get_count_raw(&rc), 0, "released");
211 T_ASSERT_EQ_UINT(x, 0, "returned released");
212 }
213
214 static void
do_bitwise_test(const os_ref_count_t bits)215 do_bitwise_test(const os_ref_count_t bits)
216 {
217 os_ref_atomic_t rc;
218 os_ref_count_t reserved = 0xaaaaaaaaU & ((1U << bits) - 1);
219
220 T_LOG("do_bitwise_test(nbits:%d, reserved:%#x)", bits, reserved);
221
222 os_ref_init_count_mask(&rc, bits, NULL, 1, reserved);
223
224 T_ASSERT_EQ_UINT(os_ref_get_count_mask(&rc, bits), 1, "[%u bits] refcount initialized", bits);
225
226 os_ref_retain_mask(&rc, bits, NULL);
227 os_ref_retain_mask(&rc, bits, NULL);
228 T_ASSERT_EQ_UINT(os_ref_get_count_mask(&rc, bits), 3, "retain increased count");
229
230 os_ref_count_t x = os_ref_release_mask(&rc, bits, NULL);
231 T_ASSERT_EQ_UINT(x, 2, "release returned correct count");
232
233 os_ref_release_live_mask(&rc, bits, NULL);
234 T_ASSERT_EQ_UINT(os_ref_get_count_mask(&rc, bits), 1, "release_live decreased count");
235
236 x = os_ref_release_mask(&rc, bits, NULL);
237 T_ASSERT_EQ_UINT(os_ref_get_count_mask(&rc, bits), 0, "released");
238 T_ASSERT_EQ_UINT(x, 0, "returned released");
239
240 T_ASSERT_EQ_UINT(rc & ((1U << bits) - 1), reserved, "Reserved bits not modified");
241
242 os_ref_init_count_mask(&rc, bits, NULL, 1, reserved);
243 T_ASSERT_TRUE(os_ref_retain_try_mask(&rc, bits, 0, NULL), "try retained");
244 if (reserved) {
245 T_ASSERT_FALSE(os_ref_retain_try_mask(&rc, bits, reserved, NULL), "try reject");
246 }
247
248 (void)os_ref_release_mask(&rc, bits, NULL);
249 (void)os_ref_release_mask(&rc, bits, NULL);
250 T_QUIET; T_ASSERT_EQ_UINT(os_ref_get_count_mask(&rc, bits), 0, "release");
251
252 T_ASSERT_FALSE(os_ref_retain_try_mask(&rc, bits, 0, NULL), "try fail");
253
254 T_ASSERT_EQ_UINT(os_ref_get_bits_mask(&rc, bits), reserved, "Reserved bits not modified");
255 }
256
257 T_DECL(refcnt_bitwise, "Bitwise refcount")
258 {
259 do_bitwise_test(0);
260 do_bitwise_test(1);
261 do_bitwise_test(8);
262 do_bitwise_test(26);
263
264 os_ref_atomic_t rc = 0xaaaaaaaa;
265
266 const os_ref_count_t nbits = 3;
267 const os_ref_count_t count = 5;
268 const os_ref_count_t bits = 7;
269 os_ref_init_count_mask(&rc, nbits, NULL, count, bits);
270
271 os_ref_count_t mask = (1U << nbits) - 1;
272 T_ASSERT_EQ_UINT(rc & mask, bits, "bits correctly initialized");
273 T_ASSERT_EQ_UINT(rc >> nbits, count, "count correctly initialized");
274 }
275
276 os_refgrp_decl(static, g1, "test group", NULL);
277 os_refgrp_decl_extern(g1);
278
279 T_DECL(refcnt_groups, "Group accounting")
280 {
281 #if OS_REFCNT_DEBUG
282 ref_debug_enable = true;
283
284 struct os_refcnt rc;
285 os_ref_init(&rc, &g1);
286
287 T_ASSERT_EQ_UINT(g1.grp_children, 1, "group attached");
288 T_ASSERT_EQ_UINT(global_ref_group.grp_children, 1, "global group attached");
289 T_ASSERT_EQ_UINT(g1.grp_count, 1, "group count");
290 T_ASSERT_EQ_ULLONG(g1.grp_retain_total, 1ULL, "group retains");
291 T_ASSERT_EQ_ULLONG(g1.grp_release_total, 0ULL, "group releases");
292
293 os_ref_retain(&rc);
294 os_ref_retain(&rc);
295 os_ref_release_live(&rc);
296 os_ref_release_live(&rc);
297
298 T_EXPECT_EQ_ULLONG(g1.grp_retain_total, 3ULL, "group retains");
299 T_EXPECT_EQ_ULLONG(g1.grp_release_total, 2ULL, "group releases");
300
301 os_ref_count_t x = os_ref_release(&rc);
302 T_QUIET; T_ASSERT_EQ_UINT(x, 0, "released");
303
304 T_ASSERT_EQ_UINT(g1.grp_children, 0, "group detatched");
305 T_ASSERT_EQ_UINT(g1.grp_count, 0, "group count");
306 #else
307 T_SKIP("Refcount debugging disabled");
308 #endif
309 }
310
311 enum {
312 OSREF_UNDERFLOW = 1,
313 OSREF_OVERFLOW = 2,
314 OSREF_RETAIN = 3,
315 OSREF_DEALLOC_LIVE = 4,
316 };
317
318 static jmp_buf jb;
319 static bool expect_panic = false;
320
321 void
handle_panic(const char * func,char * __unused str,...)322 handle_panic(const char *func, char *__unused str, ...)
323 {
324 int ret = -1;
325 if (!expect_panic) {
326 T_FAIL("unexpected panic from %s", func);
327 T_LOG("corrupt program state, aborting");
328 abort();
329 }
330 expect_panic = false;
331
332 if (strcmp(func, "os_ref_panic_underflow") == 0) {
333 ret = OSREF_UNDERFLOW;
334 } else if (strcmp(func, "os_ref_panic_overflow") == 0) {
335 ret = OSREF_OVERFLOW;
336 } else if (strcmp(func, "os_ref_panic_retain") == 0) {
337 ret = OSREF_RETAIN;
338 } else if (strcmp(func, "os_ref_panic_live") == 0) {
339 ret = OSREF_DEALLOC_LIVE;
340 } else {
341 T_LOG("unexpected panic from %s", func);
342 }
343
344 longjmp(jb, ret);
345 }
346
347 T_DECL(refcnt_underflow, "Underflow")
348 {
349 os_ref_atomic_t rc;
350 os_ref_init_raw(&rc, NULL);
351 (void)os_ref_release_raw(&rc, NULL);
352
353 int x = setjmp(jb);
354 if (x == 0) {
355 expect_panic = true;
356 (void)os_ref_release_raw(&rc, NULL);
357 T_FAIL("underflow not caught");
358 } else {
359 T_ASSERT_EQ_INT(x, OSREF_UNDERFLOW, "underflow caught");
360 }
361 }
362
363 T_DECL(refcnt_overflow, "Overflow")
364 {
365 os_ref_atomic_t rc;
366 os_ref_init_count_raw(&rc, NULL, 0x0fffffffU);
367
368 int x = setjmp(jb);
369 if (x == 0) {
370 expect_panic = true;
371 (void)os_ref_retain_raw(&rc, NULL);
372 T_FAIL("overflow not caught");
373 } else {
374 T_ASSERT_EQ_INT(x, OSREF_RETAIN, "overflow caught");
375 }
376 }
377
378 T_DECL(refcnt_resurrection, "Resurrection")
379 {
380 os_ref_atomic_t rc;
381 os_ref_init_raw(&rc, NULL);
382 os_ref_count_t n = os_ref_release_raw(&rc, NULL);
383
384 T_QUIET; T_EXPECT_EQ_UINT(n, 0, "reference not released");
385
386 int x = setjmp(jb);
387 if (x == 0) {
388 expect_panic = true;
389 (void)os_ref_retain_raw(&rc, NULL);
390 T_FAIL("resurrection not caught");
391 } else {
392 T_ASSERT_EQ_INT(x, OSREF_RETAIN, "resurrection caught");
393 }
394 }
395
396 T_DECL(refcnt_dealloc_live, "Dealloc expected live object")
397 {
398 os_ref_atomic_t rc;
399 os_ref_init_raw(&rc, NULL);
400
401 expect_panic = true;
402 int x = setjmp(jb);
403 if (x == 0) {
404 expect_panic = true;
405 os_ref_release_live_raw(&rc, NULL);
406 T_FAIL("dealloc live not caught");
407 } else {
408 T_ASSERT_EQ_INT(x, OSREF_DEALLOC_LIVE, "dealloc live caught");
409 }
410 }
411
412 T_DECL(refcnt_initializer, "Static intializers")
413 {
414 struct os_refcnt rc = OS_REF_INITIALIZER;
415 os_ref_atomic_t rca = OS_REF_ATOMIC_INITIALIZER;
416
417 T_ASSERT_EQ_INT(0, os_ref_retain_try(&rc), NULL);
418 T_ASSERT_EQ_INT(0, os_ref_get_count_raw(&rca), NULL);
419 }
420
421 #if STRESS_TESTS
422
423 static unsigned pcpu_perf_step = 0;
424
425 static void
worker_ref(os_ref_atomic_t * rc,unsigned long * count)426 worker_ref(os_ref_atomic_t *rc, unsigned long *count)
427 {
428 unsigned long n = 0;
429
430 while (os_atomic_load(&pcpu_perf_step, relaxed) == 0) {
431 }
432
433 while (os_atomic_load(&pcpu_perf_step, relaxed) == 1) {
434 os_ref_retain_raw(rc, NULL);
435 os_ref_release_live_raw(rc, NULL);
436 n++;
437 }
438
439 os_atomic_add(count, n, relaxed);
440 }
441
442 static void
worker_pcpu_ref(os_pcpu_ref_t rc,unsigned long * count)443 worker_pcpu_ref(os_pcpu_ref_t rc, unsigned long *count)
444 {
445 unsigned long n = 0;
446
447 while (os_atomic_load(&pcpu_perf_step, relaxed) == 0) {
448 }
449
450 while (os_atomic_load(&pcpu_perf_step, relaxed) == 1) {
451 os_pcpu_ref_retain(rc, NULL);
452 os_pcpu_ref_release_live(rc, NULL);
453 n++;
454 }
455
456 os_atomic_add(count, n, relaxed);
457 }
458
459 #define PCPU_BENCH_LEN 2
460
461 static void
warmup_thread_pool(dispatch_group_t g,dispatch_queue_t rq)462 warmup_thread_pool(dispatch_group_t g, dispatch_queue_t rq)
463 {
464 os_atomic_store(&pcpu_perf_step, 1, relaxed);
465
466 zpercpu_foreach_cpu(cpu) {
467 dispatch_group_async(g, rq, ^{
468 while (os_atomic_load(&pcpu_perf_step, relaxed) == 1) {
469 }
470 });
471 }
472
473 os_atomic_store(&pcpu_perf_step, 0, relaxed);
474 dispatch_group_wait(g, DISPATCH_TIME_FOREVER);
475 }
476
477 T_DECL(pcpu_perf, "Performance per-cpu")
478 {
479 os_ref_atomic_t rc;
480 os_pcpu_ref_t prc;
481 __block unsigned long count = 0;
482 double scale = PCPU_BENCH_LEN * 1e6;
483 dispatch_queue_t rq = dispatch_get_global_queue(QOS_CLASS_USER_INITIATED, 0);
484 dispatch_group_t g = dispatch_group_create();
485
486 os_ref_init_raw(&rc, NULL);
487 os_pcpu_ref_init(&prc, NULL);
488
489 T_LOG("uncontended benchmark");
490
491 dispatch_group_async(g, rq, ^{
492 worker_ref(&rc, &count);
493 });
494
495 count = 0;
496 os_atomic_store(&pcpu_perf_step, 1, relaxed);
497 sleep(PCPU_BENCH_LEN);
498 os_atomic_store(&pcpu_perf_step, 0, relaxed);
499 dispatch_group_wait(g, DISPATCH_TIME_FOREVER);
500
501 T_PASS("%.2fM rounds per thread per second (atomic)", count / scale);
502
503 dispatch_group_async(g, rq, ^{
504 worker_pcpu_ref(prc, &count);
505 });
506
507 count = 0;
508 os_atomic_store(&pcpu_perf_step, 1, relaxed);
509 sleep(PCPU_BENCH_LEN);
510 os_atomic_store(&pcpu_perf_step, 0, relaxed);
511 dispatch_group_wait(g, DISPATCH_TIME_FOREVER);
512
513 T_PASS("%.2fM rounds per thread per second (pcpu)", count / scale);
514
515 T_LOG("contended benchmark");
516
517 warmup_thread_pool(g, rq);
zpercpu_foreach_cpu(cpu)518 zpercpu_foreach_cpu(cpu) {
519 dispatch_group_async(g, rq, ^{
520 worker_ref(&rc, &count);
521 });
522 }
523
524 count = 0;
525 os_atomic_store(&pcpu_perf_step, 1, relaxed);
526 sleep(PCPU_BENCH_LEN);
527 os_atomic_store(&pcpu_perf_step, 0, relaxed);
528 dispatch_group_wait(g, DISPATCH_TIME_FOREVER);
529
530 T_PASS("%.2fM rounds per thread per second (atomic)", count / (zpercpu_count() * scale));
531
532 warmup_thread_pool(g, rq);
zpercpu_foreach_cpu(cpu)533 zpercpu_foreach_cpu(cpu) {
534 dispatch_group_async(g, rq, ^{
535 worker_pcpu_ref(prc, &count);
536 });
537 }
538
539 count = 0;
540 os_atomic_store(&pcpu_perf_step, 1, relaxed);
541 sleep(PCPU_BENCH_LEN);
542 os_atomic_store(&pcpu_perf_step, 0, relaxed);
543 dispatch_group_wait(g, DISPATCH_TIME_FOREVER);
544
545 T_PASS("%.2fM rounds per thread per second (pcpu)", count / (zpercpu_count() * scale));
546
547 (void)os_pcpu_ref_kill(prc, NULL);
548 os_pcpu_ref_destroy(&prc, NULL);
549 }
550
551 static const unsigned long iters = 1024 * 1024 * 32;
552
553 static void *
func(void * _rc)554 func(void *_rc)
555 {
556 struct os_refcnt *rc = _rc;
557 for (unsigned long i = 0; i < iters; i++) {
558 os_ref_retain(rc);
559 os_ref_release_live(rc);
560 }
561 return NULL;
562 }
563
564 T_DECL(refcnt_stress, "Stress test")
565 {
566 pthread_t th1, th2;
567
568 struct os_refcnt rc;
569 os_ref_init(&rc, NULL);
570
571 T_ASSERT_POSIX_ZERO(pthread_create(&th1, NULL, func, &rc), "pthread_create");
572 T_ASSERT_POSIX_ZERO(pthread_create(&th2, NULL, func, &rc), "pthread_create");
573
574 void *r1, *r2;
575 T_ASSERT_POSIX_ZERO(pthread_join(th1, &r1), "pthread_join");
576 T_ASSERT_POSIX_ZERO(pthread_join(th2, &r2), "pthread_join");
577
578 os_ref_count_t x = os_ref_release(&rc);
579 T_ASSERT_EQ_INT(x, 0, "Consistent refcount");
580 }
581
582 #endif
583