]> git.saurik.com Git - apple/xnu.git/blob - tools/tests/zero-to-n/zero-to-n.c
xnu-2782.1.97.tar.gz
[apple/xnu.git] / tools / tests / zero-to-n / zero-to-n.c
1 /*
2 * Copyright (c) 2009 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 #include <unistd.h>
29 #include <stdio.h>
30 #include <math.h>
31 #include <sys/wait.h>
32 #include <sys/param.h>
33 #include <sys/syscall.h>
34 #include <sys/types.h>
35 #include <sys/ptrace.h>
36 #include <semaphore.h>
37 #include <stdlib.h>
38 #include <pthread.h>
39 #include <fcntl.h>
40 #include <errno.h>
41 #include <err.h>
42 #include <string.h>
43
44 #include <spawn.h>
45 #include <spawn_private.h>
46 #include <sys/spawn_internal.h>
47 #include <mach-o/dyld.h>
48
49 #include <libkern/OSAtomic.h>
50
51 #include <mach/mach_time.h>
52 #include <mach/mach.h>
53 #include <mach/task.h>
54 #include <mach/semaphore.h>
55
56 typedef enum wake_type { WAKE_BROADCAST_ONESEM, WAKE_BROADCAST_PERTHREAD, WAKE_CHAIN } wake_type_t;
57 typedef enum my_policy_type { MY_POLICY_REALTIME, MY_POLICY_TIMESHARE, MY_POLICY_FIXEDPRI } my_policy_type_t;
58
59 #define assert(truth, label) do { if(!(truth)) { printf("Thread %p: failure on line %d\n", pthread_self(), __LINE__); goto label; } } while (0)
60
61 #define CONSTRAINT_NANOS (20000000ll) /* 20 ms */
62 #define COMPUTATION_NANOS (10000000ll) /* 10 ms */
63 #define TRACEWORTHY_NANOS (10000000ll) /* 10 ms */
64
65 #if DEBUG
66 #define debug_log(args...) printf(args)
67 #else
68 #define debug_log(args...) do { } while(0)
69 #endif
70
71 /* Declarations */
72 void* child_thread_func(void *arg);
73 void print_usage();
74 int thread_setup(int my_id);
75 my_policy_type_t parse_thread_policy(const char *str);
76 int thread_finish_iteration();
77 void selfexec_with_apptype(int argc, char *argv[]);
78
79 /* Global variables (general) */
80 int g_numthreads;
81 wake_type_t g_waketype;
82 policy_t g_policy;
83 int g_iterations;
84 struct mach_timebase_info g_mti;
85 semaphore_t g_main_sem;
86 uint64_t *g_thread_endtimes_abs;
87 volatile int32_t g_done_threads;
88 boolean_t g_do_spin = FALSE;
89 boolean_t g_verbose = FALSE;
90 boolean_t g_do_affinity = FALSE;
91 uint64_t g_starttime_abs;
92 #if MIMIC_DIGI_LEAD_TIME
93 int g_long_spinid;
94 uint64_t g_spinlength_abs;
95 #endif /* MIMIC_DIGI_LEAD_TIME */
96
97 /* Global variables (broadcast) */
98 semaphore_t g_machsem;
99 semaphore_t g_leadersem;
100
101 /* Global variables (chain) */
102 semaphore_t *g_semarr;
103
104 uint64_t
105 abs_to_nanos(uint64_t abstime)
106 {
107 return (uint64_t)(abstime * (((double)g_mti.numer) / ((double)g_mti.denom)));
108 }
109
110 uint64_t
111 nanos_to_abs(uint64_t ns)
112 {
113 return (uint64_t)(ns * (((double)g_mti.denom) / ((double)g_mti.numer)));
114 }
115
116 /*
117 * Figure out what thread policy to use
118 */
119 my_policy_type_t
120 parse_thread_policy(const char *str)
121 {
122 if (strcmp(str, "timeshare") == 0) {
123 return MY_POLICY_TIMESHARE;
124 } else if (strcmp(str, "realtime") == 0) {
125 return MY_POLICY_REALTIME;
126 } else if (strcmp(str, "fixed") == 0) {
127 return MY_POLICY_FIXEDPRI;
128 } else {
129 printf("Invalid thread policy %s\n", str);
130 exit(1);
131 }
132 }
133
134 /*
135 * Figure out what wakeup pattern to use
136 */
137 wake_type_t
138 parse_wakeup_pattern(const char *str)
139 {
140 if (strcmp(str, "chain") == 0) {
141 return WAKE_CHAIN;
142 } else if (strcmp(str, "broadcast-single-sem") == 0) {
143 return WAKE_BROADCAST_ONESEM;
144 } else if (strcmp(str, "broadcast-per-thread") == 0) {
145 return WAKE_BROADCAST_PERTHREAD;
146 } else {
147 print_usage();
148 exit(1);
149 }
150 }
151
152 /*
153 * Set policy
154 */
155 int
156 thread_setup(int my_id)
157 {
158 int res;
159
160 switch (g_policy) {
161 case MY_POLICY_TIMESHARE:
162 {
163 res = KERN_SUCCESS;
164 break;
165 }
166 case MY_POLICY_REALTIME:
167 {
168 thread_time_constraint_policy_data_t pol;
169
170 /* Hard-coded realtime parameters (similar to what Digi uses) */
171 pol.period = 100000;
172 pol.constraint = nanos_to_abs(CONSTRAINT_NANOS);
173 pol.computation = nanos_to_abs(COMPUTATION_NANOS);
174 pol.preemptible = 0; /* Ignored by OS */
175
176 res = thread_policy_set(mach_thread_self(), THREAD_TIME_CONSTRAINT_POLICY, (thread_policy_t) &pol, THREAD_TIME_CONSTRAINT_POLICY_COUNT);
177 assert(res == 0, fail);
178 break;
179 }
180 case MY_POLICY_FIXEDPRI:
181 {
182 thread_extended_policy_data_t pol;
183 pol.timeshare = 0;
184
185 res = thread_policy_set(mach_thread_self(), THREAD_EXTENDED_POLICY, (thread_policy_t) &pol, THREAD_EXTENDED_POLICY_COUNT);
186 assert(res == 0, fail);
187 break;
188 }
189 default:
190 {
191 printf("invalid policy type\n");
192 return 1;
193 }
194 }
195
196 if (g_do_affinity) {
197 thread_affinity_policy_data_t affinity;
198
199 affinity.affinity_tag = my_id % 2;
200
201 res = thread_policy_set(mach_thread_self(), THREAD_AFFINITY_POLICY, (thread_policy_t)&affinity, THREAD_AFFINITY_POLICY_COUNT);
202 assert(res == 0, fail);
203 }
204
205 return 0;
206 fail:
207 return 1;
208 }
209
210 /*
211 * Wake up main thread if everyone's done
212 */
213 int
214 thread_finish_iteration(int id)
215 {
216 int32_t new;
217 int res = 0;
218 volatile float x = 0.0;
219 volatile float y = 0.0;
220
221 debug_log("Thread %p finished iteration.\n", pthread_self());
222
223 #if MIMIC_DIGI_LEAD_TIME
224 /*
225 * One randomly chosen thread determines when everybody gets to stop.
226 */
227 if (g_do_spin) {
228 if (g_long_spinid == id) {
229 uint64_t endspin;
230
231 /* This thread took up fully half of his computation */
232 endspin = g_starttime_abs + g_spinlength_abs;
233 while (mach_absolute_time() < endspin) {
234 y = y + 1.5 + x;
235 x = sqrt(y);
236 }
237 }
238 }
239 #endif /* MIMIC_DIGI_LEAD_TIME */
240
241 new = OSAtomicIncrement32(&g_done_threads);
242
243 debug_log("New value is %d\n", new);
244
245 /*
246 * When the last thread finishes, everyone gets to go back to sleep.
247 */
248 if (new == g_numthreads) {
249 debug_log("Thread %p signalling main thread.\n", pthread_self());
250 res = semaphore_signal(g_main_sem);
251 } else {
252 #ifndef MIMIC_DIGI_LEAD_TIME
253 if (g_do_spin) {
254 while (g_done_threads < g_numthreads) {
255 y = y + 1.5 + x;
256 x = sqrt(y);
257 }
258 }
259 #endif
260 }
261
262 return res;
263 }
264
265 /*
266 * Wait for a wakeup, potentially wake up another of the "0-N" threads,
267 * and notify the main thread when done.
268 */
269 void*
270 child_thread_func(void *arg)
271 {
272 int my_id = (int)(uintptr_t)arg;
273 int res;
274 int i, j;
275 int32_t new;
276
277 /* Set policy and so forth */
278 thread_setup(my_id);
279
280 /* Tell main thread when everyone has set up */
281 new = OSAtomicIncrement32(&g_done_threads);
282 semaphore_signal(g_main_sem);
283
284 /* For each iteration */
285 for (i = 0; i < g_iterations; i++) {
286 /*
287 * Leader thread either wakes everyone up or starts the chain going.
288 */
289 if (my_id == 0) {
290 res = semaphore_wait(g_leadersem);
291 assert(res == 0, fail);
292
293 g_thread_endtimes_abs[my_id] = mach_absolute_time();
294
295 #if MIMIC_DIGI_LEAD_TIME
296 g_long_spinid = rand() % g_numthreads;
297 #endif /* MIMIC_DIGI_LEAD_TIME */
298
299 switch (g_waketype) {
300 case WAKE_CHAIN:
301 semaphore_signal(g_semarr[my_id + 1]);
302 break;
303 case WAKE_BROADCAST_ONESEM:
304 semaphore_signal_all(g_machsem);
305 break;
306 case WAKE_BROADCAST_PERTHREAD:
307 for (j = 1; j < g_numthreads; j++) {
308 semaphore_signal(g_semarr[j]);
309 }
310 break;
311 default:
312 printf("Invalid wakeup type?!\n");
313 exit(1);
314 }
315 } else {
316 /*
317 * Everyone else waits to be woken up,
318 * records when she wake up, and possibly
319 * wakes up a friend.
320 */
321 switch(g_waketype) {
322 case WAKE_BROADCAST_ONESEM:
323 res = semaphore_wait(g_machsem);
324 assert(res == KERN_SUCCESS, fail);
325
326 g_thread_endtimes_abs[my_id] = mach_absolute_time();
327
328 break;
329 /*
330 * For the chain wakeup case:
331 * wait, record time, signal next thread if appropriate
332 */
333 case WAKE_BROADCAST_PERTHREAD:
334 res = semaphore_wait(g_semarr[my_id]);
335 assert(res == 0, fail);
336
337 g_thread_endtimes_abs[my_id] = mach_absolute_time();
338 break;
339
340 case WAKE_CHAIN:
341 res = semaphore_wait(g_semarr[my_id]);
342 assert(res == 0, fail);
343
344 g_thread_endtimes_abs[my_id] = mach_absolute_time();
345
346 if (my_id < (g_numthreads - 1)) {
347 res = semaphore_signal(g_semarr[my_id + 1]);
348 assert(res == 0, fail);
349 }
350
351 break;
352 default:
353 printf("Invalid wake type.\n");
354 goto fail;
355 }
356 }
357
358 res = thread_finish_iteration(my_id);
359 assert(res == 0, fail);
360 }
361
362 return 0;
363 fail:
364 exit(1);
365 }
366
367 /*
368 * Admittedly not very attractive.
369 */
370 void
371 print_usage()
372 {
373 printf("Usage: zn <num threads> <chain | broadcast-single-sem | broadcast-per-thread> <realtime | timeshare | fixed> <num iterations> [-trace <traceworthy latency in ns>] [-spin] [-affinity] [-verbose]\n");
374 }
375
376 /*
377 * Given an array of uint64_t values, compute average, max, min, and standard deviation
378 */
379 void
380 compute_stats(uint64_t *values, uint64_t count, float *averagep, uint64_t *maxp, uint64_t *minp, float *stddevp)
381 {
382 int i;
383 uint64_t _sum = 0;
384 uint64_t _max = 0;
385 uint64_t _min = UINT64_MAX;
386 float _avg = 0;
387 float _dev = 0;
388
389 for (i = 0; i < count; i++) {
390 _sum += values[i];
391 _max = values[i] > _max ? values[i] : _max;
392 _min = values[i] < _min ? values[i] : _min;
393 }
394
395 _avg = ((float)_sum) / ((float)count);
396
397 _dev = 0;
398 for (i = 0; i < count; i++) {
399 _dev += powf((((float)values[i]) - _avg), 2);
400 }
401
402 _dev /= count;
403 _dev = sqrtf(_dev);
404
405 *averagep = _avg;
406 *maxp = _max;
407 *minp = _min;
408 *stddevp = _dev;
409 }
410
411 int
412 main(int argc, char **argv)
413 {
414 int i;
415 int res;
416 pthread_t *threads;
417 uint64_t *worst_latencies_ns;
418 uint64_t *worst_latencies_from_first_ns;
419 uint64_t last_end;
420 uint64_t max, min;
421 uint64_t traceworthy_latency_ns = TRACEWORTHY_NANOS;
422 float avg, stddev;
423 boolean_t seen_apptype = FALSE;
424
425 srand(time(NULL));
426
427 if (argc < 5 || argc > 10) {
428 print_usage();
429 goto fail;
430 }
431
432 /* How many threads? */
433 g_numthreads = atoi(argv[1]);
434
435 /* What wakeup pattern? */
436 g_waketype = parse_wakeup_pattern(argv[2]);
437
438 /* Policy */
439 g_policy = parse_thread_policy(argv[3]);
440
441 /* Iterations */
442 g_iterations = atoi(argv[4]);
443
444 /* Optional args */
445 for (i = 5; i < argc; i++) {
446 if (strcmp(argv[i], "-spin") == 0) {
447 g_do_spin = TRUE;
448 } else if (strcmp(argv[i], "-verbose") == 0) {
449 g_verbose = TRUE;
450 } else if ((strcmp(argv[i], "-trace") == 0) &&
451 (i < (argc - 1))) {
452 traceworthy_latency_ns = strtoull(argv[++i], NULL, 10);
453 } else if (strcmp(argv[i], "-affinity") == 0) {
454 g_do_affinity = TRUE;
455 } else if (strcmp(argv[i], "-switched_apptype") == 0) {
456 seen_apptype = TRUE;
457 } else {
458 print_usage();
459 goto fail;
460 }
461 }
462
463 if (!seen_apptype) {
464 selfexec_with_apptype(argc, argv);
465 }
466
467 mach_timebase_info(&g_mti);
468
469 #if MIMIC_DIGI_LEAD_TIME
470 g_spinlength_abs = nanos_to_abs(COMPUTATION_NANOS) / 2;
471 #endif /* MIMIC_DIGI_LEAD_TIME */
472
473 /* Arrays for threads and their wakeup times */
474 threads = (pthread_t*) malloc(sizeof(pthread_t) * g_numthreads);
475 assert(threads, fail);
476
477 g_thread_endtimes_abs = (uint64_t*) malloc(sizeof(uint64_t) * g_numthreads);
478 assert(g_thread_endtimes_abs, fail);
479
480 worst_latencies_ns = (uint64_t*) malloc(sizeof(uint64_t) * g_iterations);
481 assert(worst_latencies_ns, fail);
482
483 worst_latencies_from_first_ns = (uint64_t*) malloc(sizeof(uint64_t) * g_iterations);
484 assert(worst_latencies_from_first_ns, fail);
485 res = semaphore_create(mach_task_self(), &g_main_sem, SYNC_POLICY_FIFO, 0);
486 assert(res == KERN_SUCCESS, fail);
487
488 /* Either one big semaphore or one per thread */
489 if (g_waketype == WAKE_CHAIN || g_waketype == WAKE_BROADCAST_PERTHREAD) {
490 g_semarr = malloc(sizeof(semaphore_t) * g_numthreads);
491 assert(g_semarr != NULL, fail);
492
493 for (i = 0; i < g_numthreads; i++) {
494 res = semaphore_create(mach_task_self(), &g_semarr[i], SYNC_POLICY_FIFO, 0);
495 assert(res == KERN_SUCCESS, fail);
496 }
497
498 g_leadersem = g_semarr[0];
499 } else {
500 res = semaphore_create(mach_task_self(), &g_machsem, SYNC_POLICY_FIFO, 0);
501 assert(res == KERN_SUCCESS, fail);
502 res = semaphore_create(mach_task_self(), &g_leadersem, SYNC_POLICY_FIFO, 0);
503 assert(res == KERN_SUCCESS, fail);
504 }
505
506 /* Create the threads */
507 g_done_threads = 0;
508 for (i = 0; i < g_numthreads; i++) {
509 res = pthread_create(&threads[i], NULL, child_thread_func, (void*)(uintptr_t)i);
510 assert(res == 0, fail);
511 }
512
513 res = setpriority(PRIO_DARWIN_ROLE, 0, PRIO_DARWIN_ROLE_UI_FOCAL);
514 assert(res == 0, fail);
515 thread_setup(0);
516
517 /* Switching to fixed pri may have stripped our main thread QoS and priority, so re-instate */
518 if (g_policy == MY_POLICY_FIXEDPRI) {
519 thread_precedence_policy_data_t prec;
520 mach_msg_type_number_t count;
521 boolean_t get_default = FALSE;
522
523 count = THREAD_PRECEDENCE_POLICY_COUNT;
524 res = thread_policy_get(mach_thread_self(), THREAD_PRECEDENCE_POLICY, (thread_policy_t) &prec, &count, &get_default);
525 assert(res == 0, fail);
526
527 prec.importance += 16; /* 47 - 31 */
528 res = thread_policy_set(mach_thread_self(), THREAD_PRECEDENCE_POLICY, (thread_policy_t) &prec, THREAD_PRECEDENCE_POLICY_COUNT);
529 assert(res == 0, fail);
530 }
531
532 /* Let everyone get settled */
533 for (i = 0; i < g_numthreads; i++) {
534 res = semaphore_wait(g_main_sem);
535 assert(res == 0, fail);
536 }
537 /* Let worker threads get back to sleep... */
538 usleep(g_numthreads * 10);
539
540 /* Go! */
541 for (i = 0; i < g_iterations; i++) {
542 int j;
543 uint64_t worst_abs = 0, best_abs = UINT64_MAX;
544
545 g_done_threads = 0;
546 OSMemoryBarrier();
547
548 g_starttime_abs = mach_absolute_time();
549
550 /* Fire them off */
551 semaphore_signal(g_leadersem);
552
553 /* Wait for worker threads to finish */
554 semaphore_wait(g_main_sem);
555 assert(res == KERN_SUCCESS, fail);
556
557 /*
558 * We report the worst latencies relative to start time
559 * and relative to the lead worker thread.
560 */
561 for (j = 0; j < g_numthreads; j++) {
562 uint64_t latency_abs;
563
564 latency_abs = g_thread_endtimes_abs[j] - g_starttime_abs;
565 worst_abs = worst_abs < latency_abs ? latency_abs : worst_abs;
566 }
567
568 worst_latencies_ns[i] = abs_to_nanos(worst_abs);
569
570 worst_abs = 0;
571 for (j = 1; j < g_numthreads; j++) {
572 uint64_t latency_abs;
573
574 latency_abs = g_thread_endtimes_abs[j] - g_thread_endtimes_abs[0];
575 worst_abs = worst_abs < latency_abs ? latency_abs : worst_abs;
576 best_abs = best_abs > latency_abs ? latency_abs : best_abs;
577 }
578
579 worst_latencies_from_first_ns[i] = abs_to_nanos(worst_abs);
580
581 /*
582 * In the event of a bad run, cut a trace point.
583 */
584 if (worst_latencies_from_first_ns[i] > traceworthy_latency_ns) {
585 int _tmp;
586
587 if (g_verbose) {
588 printf("Worst on this round was %.2f us.\n", ((float)worst_latencies_from_first_ns[i]) / 1000.0);
589 }
590
591 _tmp = syscall(SYS_kdebug_trace, 0xEEEEEEEE, 0, 0, 0, 0);
592 }
593
594 /* Let worker threads get back to sleep... */
595 usleep(g_numthreads * 10);
596 }
597
598 /* Rejoin threads */
599 last_end = 0;
600 for (i = 0; i < g_numthreads; i++) {
601 res = pthread_join(threads[i], NULL);
602 assert(res == 0, fail);
603 }
604
605 compute_stats(worst_latencies_ns, g_iterations, &avg, &max, &min, &stddev);
606 printf("Results (from a stop):\n");
607 printf("Max:\t\t%.2f us\n", ((float)max) / 1000.0);
608 printf("Min:\t\t%.2f us\n", ((float)min) / 1000.0);
609 printf("Avg:\t\t%.2f us\n", avg / 1000.0);
610 printf("Stddev:\t\t%.2f us\n", stddev / 1000.0);
611
612 putchar('\n');
613
614 compute_stats(worst_latencies_from_first_ns, g_iterations, &avg, &max, &min, &stddev);
615 printf("Results (relative to first thread):\n");
616 printf("Max:\t\t%.2f us\n", ((float)max) / 1000.0);
617 printf("Min:\t\t%.2f us\n", ((float)min) / 1000.0);
618 printf("Avg:\t\t%.2f us\n", avg / 1000.0);
619 printf("Stddev:\t\t%.2f us\n", stddev / 1000.0);
620
621 #if 0
622 for (i = 0; i < g_iterations; i++) {
623 printf("Iteration %d: %f us\n", i, worst_latencies_ns[i] / 1000.0);
624 }
625 #endif
626
627 return 0;
628 fail:
629 return 1;
630 }
631
632 /*
633 * WARNING: This is SPI specifically intended for use by launchd to start UI
634 * apps. We use it here for a test tool only to opt into QoS using the same
635 * policies. Do not use this outside xnu or libxpc/launchd.
636 */
637 void
638 selfexec_with_apptype(int argc, char *argv[])
639 {
640 int ret;
641 posix_spawnattr_t attr;
642 extern char **environ;
643 char *new_argv[argc + 1 + 1 /* NULL */];
644 int i;
645 char prog[PATH_MAX];
646 int32_t prog_size = PATH_MAX;
647
648 ret = _NSGetExecutablePath(prog, &prog_size);
649 if (ret != 0) err(1, "_NSGetExecutablePath");
650
651 for (i=0; i < argc; i++) {
652 new_argv[i] = argv[i];
653 }
654
655 new_argv[i] = "-switched_apptype";
656 new_argv[i+1] = NULL;
657
658 ret = posix_spawnattr_init(&attr);
659 if (ret != 0) errc(1, ret, "posix_spawnattr_init");
660
661 ret = posix_spawnattr_setflags(&attr, POSIX_SPAWN_SETEXEC);
662 if (ret != 0) errc(1, ret, "posix_spawnattr_setflags");
663
664 ret = posix_spawnattr_setprocesstype_np(&attr, POSIX_SPAWN_PROC_TYPE_APP_DEFAULT);
665 if (ret != 0) errc(1, ret, "posix_spawnattr_setprocesstype_np");
666
667 ret = posix_spawn(NULL, prog, NULL, &attr, new_argv, environ);
668 if (ret != 0) errc(1, ret, "posix_spawn");
669 }