[apple/xnu.git] / tools / tests / zero-to-n / zero-to-n.c

/*
 * Copyright (c) 2009 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@
 */
#include <unistd.h>
#include <stdio.h>
#include <math.h>
#include <sys/wait.h>
#include <sys/param.h>
#include <sys/kdebug.h>
#include <sys/types.h>
#include <sys/ptrace.h>
#include <semaphore.h>
#include <stdlib.h>
#include <pthread.h>
#include <fcntl.h>
#include <errno.h>
#include <err.h>
#include <string.h>

#include <spawn.h>
#include <spawn_private.h>
#include <sys/spawn_internal.h>
#include <mach-o/dyld.h>

#include <libkern/OSAtomic.h>

#include <mach/mach_time.h>
#include <mach/mach.h>
#include <mach/task.h>
#include <mach/semaphore.h>

typedef enum wake_type { WAKE_BROADCAST_ONESEM, WAKE_BROADCAST_PERTHREAD, WAKE_CHAIN } wake_type_t;
typedef enum my_policy_type { MY_POLICY_REALTIME, MY_POLICY_TIMESHARE, MY_POLICY_FIXEDPRI } my_policy_type_t;

#define assert(truth, label) do { if(!(truth)) { printf("Thread %p: failure on line %d\n", pthread_self(), __LINE__); goto label; } } while (0)

#define CONSTRAINT_NANOS	(20000000ll)	/* 20 ms */
#define COMPUTATION_NANOS	(10000000ll)	/* 10 ms */
#define TRACEWORTHY_NANOS	(10000000ll)	/* 10 ms */

#if DEBUG
#define debug_log(args...) printf(args)
#else
#define debug_log(args...) do { } while(0)
#endif

/* Declarations */
void* 			child_thread_func(void *arg);
void			print_usage();
int			thread_setup(int my_id);
my_policy_type_t	parse_thread_policy(const char *str);
int			thread_finish_iteration();
void			selfexec_with_apptype(int argc, char *argv[]);

/* Global variables (general) */
int			g_numthreads;
wake_type_t 		g_waketype;
policy_t		g_policy;
int			g_iterations;
struct mach_timebase_info g_mti;
semaphore_t		g_main_sem;
uint64_t 		*g_thread_endtimes_abs;
volatile int32_t 	g_done_threads;
boolean_t		g_do_spin = FALSE;
boolean_t		g_verbose = FALSE;
boolean_t		g_do_affinity = FALSE;
uint64_t	 	g_starttime_abs;
#if MIMIC_DIGI_LEAD_TIME
int			g_long_spinid;
uint64_t		g_spinlength_abs;
#endif /* MIMIC_DIGI_LEAD_TIME */

/* Global variables (broadcast) */
semaphore_t 		g_machsem;
semaphore_t 		g_leadersem;

/* Global variables (chain) */
semaphore_t		*g_semarr;

uint64_t
abs_to_nanos(uint64_t abstime)
{
	return (uint64_t)(abstime * (((double)g_mti.numer) / ((double)g_mti.denom)));
}

uint64_t
nanos_to_abs(uint64_t ns)
{
	return (uint64_t)(ns * (((double)g_mti.denom) / ((double)g_mti.numer)));
}

/*
 * Figure out what thread policy to use 
 */
my_policy_type_t
parse_thread_policy(const char *str)
{
	if (strcmp(str, "timeshare") == 0) {
		return MY_POLICY_TIMESHARE;
	} else if (strcmp(str, "realtime") == 0) {
		return MY_POLICY_REALTIME;
	} else if (strcmp(str, "fixed") == 0) {
		return MY_POLICY_FIXEDPRI;
	} else {
		printf("Invalid thread policy %s\n", str);
		exit(1);
	}
}

/*
 * Figure out what wakeup pattern to use
 */
wake_type_t 
parse_wakeup_pattern(const char *str) 
{
	if (strcmp(str, "chain") == 0) {
		return WAKE_CHAIN;
	} else if (strcmp(str, "broadcast-single-sem") == 0) {
		return WAKE_BROADCAST_ONESEM;
	} else if (strcmp(str, "broadcast-per-thread") == 0) {
		return WAKE_BROADCAST_PERTHREAD;
	} else {
		print_usage();
		exit(1);
	}
}

/*
 * Set policy
 */
int
thread_setup(int my_id)
{
	int res;

	switch (g_policy) {
		case MY_POLICY_TIMESHARE:
		{
			res = KERN_SUCCESS;
			break;
		}
		case MY_POLICY_REALTIME: 
		{
			thread_time_constraint_policy_data_t pol;

			/* Hard-coded realtime parameters (similar to what Digi uses) */
			pol.period = 100000;
			pol.constraint =  nanos_to_abs(CONSTRAINT_NANOS);
			pol.computation = nanos_to_abs(COMPUTATION_NANOS);
			pol.preemptible = 0; /* Ignored by OS */

			res = thread_policy_set(mach_thread_self(), THREAD_TIME_CONSTRAINT_POLICY, (thread_policy_t) &pol, THREAD_TIME_CONSTRAINT_POLICY_COUNT);
			assert(res == 0, fail);
			break;
		}
		case MY_POLICY_FIXEDPRI: 
		{
			thread_extended_policy_data_t pol;
			pol.timeshare = 0;

			res = thread_policy_set(mach_thread_self(), THREAD_EXTENDED_POLICY, (thread_policy_t) &pol, THREAD_EXTENDED_POLICY_COUNT);
			assert(res == 0, fail);
			break;
		}
		default:
		{
			printf("invalid policy type\n");
			return 1;
		}
	}

	if (g_do_affinity) {
		thread_affinity_policy_data_t affinity;

		affinity.affinity_tag = my_id % 2;

		res = thread_policy_set(mach_thread_self(), THREAD_AFFINITY_POLICY, (thread_policy_t)&affinity, THREAD_AFFINITY_POLICY_COUNT);
		assert(res == 0, fail);
	}

	return 0;
fail:
	return 1;
}

/*
 * Wake up main thread if everyone's done
 */
int
thread_finish_iteration(int id)
{
	int32_t new;
	int res = 0;
	volatile float x = 0.0;
	volatile float y = 0.0;

	debug_log("Thread %p finished iteration.\n", pthread_self());
	
#if MIMIC_DIGI_LEAD_TIME
	/*
	 * One randomly chosen thread determines when everybody gets to stop.
	 */
	if (g_do_spin) {
		if (g_long_spinid == id) {
			uint64_t endspin;

			/* This thread took up fully half of his computation */
			endspin = g_starttime_abs + g_spinlength_abs;
			while (mach_absolute_time() < endspin) {
				y = y + 1.5 + x;
				x = sqrt(y);
			}
		}
	}
#endif /* MIMIC_DIGI_LEAD_TIME */
	
	new = OSAtomicIncrement32(&g_done_threads);

	debug_log("New value is %d\n", new);

	/*
	 * When the last thread finishes, everyone gets to go back to sleep.
	 */
	if (new == g_numthreads) {
		debug_log("Thread %p signalling main thread.\n", pthread_self());
		res = semaphore_signal(g_main_sem);
	} else {
#ifndef MIMIC_DIGI_LEAD_TIME
		if (g_do_spin) {
			while (g_done_threads < g_numthreads) {
				y = y + 1.5 + x;
				x = sqrt(y);
			}
		}
#endif
	}

	return res;
}

/*
 * Wait for a wakeup, potentially wake up another of the "0-N" threads,
 * and notify the main thread when done.
 */
void*
child_thread_func(void *arg)
{
	int my_id = (int)(uintptr_t)arg;
	int res;
	int i, j;
	int32_t new;

	/* Set policy and so forth */
	thread_setup(my_id);

	/* Tell main thread when everyone has set up */
	new = OSAtomicIncrement32(&g_done_threads);
	semaphore_signal(g_main_sem);

	/* For each iteration */
	for (i = 0; i < g_iterations; i++) {
		/*
		 * Leader thread either wakes everyone up or starts the chain going.
		 */
		if (my_id == 0) { 
			res = semaphore_wait(g_leadersem);
			assert(res == 0, fail);
			
			g_thread_endtimes_abs[my_id] = mach_absolute_time();

#if MIMIC_DIGI_LEAD_TIME
			g_long_spinid = rand() % g_numthreads;
#endif /* MIMIC_DIGI_LEAD_TIME */

			switch (g_waketype) {
			case WAKE_CHAIN:
				semaphore_signal(g_semarr[my_id + 1]);
				break;
			case WAKE_BROADCAST_ONESEM: 
				semaphore_signal_all(g_machsem);
				break;
			case WAKE_BROADCAST_PERTHREAD:
				for (j = 1; j < g_numthreads; j++) {
					semaphore_signal(g_semarr[j]);
				}
				break;
			default:
				printf("Invalid wakeup type?!\n");
				exit(1);
			}
		} else {
			/*
			 * Everyone else waits to be woken up,
			 * records when she wake up, and possibly
			 * wakes up a friend.
			 */
			switch(g_waketype)  {
			case WAKE_BROADCAST_ONESEM:
				res = semaphore_wait(g_machsem);
				assert(res == KERN_SUCCESS, fail);

				g_thread_endtimes_abs[my_id] = mach_absolute_time();

				break;
				/*
				 * For the chain wakeup case:
				 * wait, record time, signal next thread if appropriate
				 */
			case WAKE_BROADCAST_PERTHREAD:
				res = semaphore_wait(g_semarr[my_id]);
				assert(res == 0, fail);

				g_thread_endtimes_abs[my_id] = mach_absolute_time();
				break;

			case WAKE_CHAIN:
				res = semaphore_wait(g_semarr[my_id]);
				assert(res == 0, fail);

				g_thread_endtimes_abs[my_id] = mach_absolute_time();

				if (my_id < (g_numthreads - 1)) {
					res = semaphore_signal(g_semarr[my_id + 1]);
					assert(res == 0, fail);
				}

				break;
			default:
				printf("Invalid wake type.\n");
				goto fail;
			}
		}

		res = thread_finish_iteration(my_id);
		assert(res == 0, fail);
	}

	return 0;
fail:
	exit(1);
}

/*
 * Admittedly not very attractive.
 */
void
print_usage()
{
	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");
}

/*
 * Given an array of uint64_t values, compute average, max, min, and standard deviation
 */
void 
compute_stats(uint64_t *values, uint64_t count, float *averagep, uint64_t *maxp, uint64_t *minp, float *stddevp)
{
	int i;
	uint64_t _sum = 0;
	uint64_t _max = 0;
	uint64_t _min = UINT64_MAX;
	float	 _avg = 0;
	float 	 _dev = 0;

	for (i = 0; i < count; i++) {
		_sum += values[i];
		_max = values[i] > _max ? values[i] : _max;
		_min = values[i] < _min ? values[i] : _min;
	}

	_avg = ((float)_sum) / ((float)count);
	
	_dev = 0;
	for (i = 0; i < count; i++) {
		_dev += powf((((float)values[i]) - _avg), 2);
	}
	
	_dev /= count;
	_dev = sqrtf(_dev);

	*averagep = _avg;
	*maxp = _max;
	*minp = _min;
	*stddevp = _dev;
}

int
main(int argc, char **argv)
{
	int		i;
	int 		res;
	pthread_t	*threads;
	uint64_t	*worst_latencies_ns;
	uint64_t	*worst_latencies_from_first_ns;
	uint64_t 	last_end;
	uint64_t	max, min;
	uint64_t	traceworthy_latency_ns = TRACEWORTHY_NANOS;
	float		avg, stddev;
	boolean_t	seen_apptype = FALSE;

	srand(time(NULL));

	if (argc < 5 || argc > 10) {
		print_usage();
		goto fail;
	}

	/* How many threads? */
	g_numthreads = atoi(argv[1]);

	/* What wakeup pattern? */
	g_waketype = parse_wakeup_pattern(argv[2]);

	/* Policy */
	g_policy = parse_thread_policy(argv[3]);

	/* Iterations */
	g_iterations = atoi(argv[4]);

	/* Optional args */
	for (i = 5; i < argc; i++) {
		if (strcmp(argv[i], "-spin") == 0) {
			g_do_spin = TRUE;
		} else if (strcmp(argv[i], "-verbose") == 0) {
			g_verbose = TRUE;
		} else if ((strcmp(argv[i], "-trace") == 0) && 
				(i < (argc - 1))) {
			traceworthy_latency_ns = strtoull(argv[++i], NULL, 10);
		} else if (strcmp(argv[i], "-affinity") == 0) {
			g_do_affinity = TRUE;
		} else if (strcmp(argv[i], "-switched_apptype") == 0) {
			seen_apptype = TRUE;
		} else {
			print_usage();
			goto fail;
		}
	}

	if (!seen_apptype) {
		selfexec_with_apptype(argc, argv);
	}

	mach_timebase_info(&g_mti);

#if MIMIC_DIGI_LEAD_TIME
	g_spinlength_abs = nanos_to_abs(COMPUTATION_NANOS) / 2;
#endif /* MIMIC_DIGI_LEAD_TIME */

	/* Arrays for threads and their wakeup times */
	threads = (pthread_t*) malloc(sizeof(pthread_t) * g_numthreads);
	assert(threads, fail);

	g_thread_endtimes_abs = (uint64_t*) malloc(sizeof(uint64_t) * g_numthreads);
	assert(g_thread_endtimes_abs, fail);

	worst_latencies_ns = (uint64_t*) malloc(sizeof(uint64_t) * g_iterations);
	assert(worst_latencies_ns, fail);

	worst_latencies_from_first_ns = (uint64_t*) malloc(sizeof(uint64_t) * g_iterations);
	assert(worst_latencies_from_first_ns, fail);
	res = semaphore_create(mach_task_self(), &g_main_sem, SYNC_POLICY_FIFO, 0);
	assert(res == KERN_SUCCESS, fail);

	/* Either one big semaphore or one per thread */
	if (g_waketype == WAKE_CHAIN || g_waketype == WAKE_BROADCAST_PERTHREAD) {
		g_semarr = malloc(sizeof(semaphore_t) * g_numthreads);
		assert(g_semarr != NULL, fail);

		for (i = 0; i < g_numthreads; i++) {
			res = semaphore_create(mach_task_self(), &g_semarr[i], SYNC_POLICY_FIFO, 0);
			assert(res == KERN_SUCCESS, fail);
		}
		
		g_leadersem = g_semarr[0];
	} else {
		res = semaphore_create(mach_task_self(), &g_machsem, SYNC_POLICY_FIFO, 0);
		assert(res == KERN_SUCCESS, fail);
		res = semaphore_create(mach_task_self(), &g_leadersem, SYNC_POLICY_FIFO, 0);
		assert(res == KERN_SUCCESS, fail);
	}

	/* Create the threads */
	g_done_threads = 0;
	for (i = 0; i < g_numthreads; i++) {
		res = pthread_create(&threads[i], NULL, child_thread_func, (void*)(uintptr_t)i);
		assert(res == 0, fail);
	}

	res = setpriority(PRIO_DARWIN_ROLE, 0, PRIO_DARWIN_ROLE_UI_FOCAL);
	assert(res == 0, fail);
	thread_setup(0);

	/* Switching to fixed pri may have stripped our main thread QoS and priority, so re-instate */
	if (g_policy == MY_POLICY_FIXEDPRI) {
		thread_precedence_policy_data_t prec;
		mach_msg_type_number_t count;
		boolean_t get_default = FALSE;
		
		count = THREAD_PRECEDENCE_POLICY_COUNT;
		res = thread_policy_get(mach_thread_self(), THREAD_PRECEDENCE_POLICY, (thread_policy_t) &prec, &count, &get_default);
		assert(res == 0, fail);
		
		prec.importance += 16; /* 47 - 31 */
		res = thread_policy_set(mach_thread_self(), THREAD_PRECEDENCE_POLICY, (thread_policy_t) &prec, THREAD_PRECEDENCE_POLICY_COUNT);
		assert(res == 0, fail);
	}

	/* Let everyone get settled */
	for (i = 0; i < g_numthreads; i++) {
		res = semaphore_wait(g_main_sem);
		assert(res == 0, fail);
	}
	/* Let worker threads get back to sleep... */
	usleep(g_numthreads * 10);

	/* Go! */
	for (i = 0; i < g_iterations; i++) {
		int j;
		uint64_t worst_abs = 0, best_abs = UINT64_MAX;

		g_done_threads = 0;
		OSMemoryBarrier();

		g_starttime_abs = mach_absolute_time();

		/* Fire them off */
		semaphore_signal(g_leadersem);

		/* Wait for worker threads to finish */
		semaphore_wait(g_main_sem);
		assert(res == KERN_SUCCESS, fail);

		/* 
		 * We report the worst latencies relative to start time
		 * and relative to the lead worker thread.
		 */
		for (j = 0; j < g_numthreads; j++) {
			uint64_t latency_abs;
		
			latency_abs = g_thread_endtimes_abs[j] - g_starttime_abs;
			worst_abs = worst_abs < latency_abs ? latency_abs : worst_abs;
		}
	
		worst_latencies_ns[i] = abs_to_nanos(worst_abs);

		worst_abs = 0;
		for (j = 1; j < g_numthreads; j++) {
			uint64_t latency_abs;
		
			latency_abs = g_thread_endtimes_abs[j] - g_thread_endtimes_abs[0];
			worst_abs = worst_abs < latency_abs ? latency_abs : worst_abs;
			best_abs = best_abs > latency_abs ? latency_abs : best_abs;
		}

		worst_latencies_from_first_ns[i] = abs_to_nanos(worst_abs);

		/*
		 * In the event of a bad run, cut a trace point.
		 */
		if (worst_latencies_from_first_ns[i] > traceworthy_latency_ns) {
			int _tmp;

			if (g_verbose) {
				printf("Worst on this round was %.2f us.\n", ((float)worst_latencies_from_first_ns[i]) / 1000.0);
			}

			_tmp = kdebug_trace(0xeeeee0 | DBG_FUNC_NONE,
								   worst_latencies_from_first_ns[i] >> 32,
								   worst_latencies_from_first_ns[i] & 0xFFFFFFFF,
								   traceworthy_latency_ns >> 32,
								   traceworthy_latency_ns & 0xFFFFFFFF);
		}

		/* Let worker threads get back to sleep... */
		usleep(g_numthreads * 10);
	}

	/* Rejoin threads */
	last_end = 0;
	for (i = 0; i < g_numthreads; i++) {
		res = pthread_join(threads[i], NULL);
		assert(res == 0, fail);
	}

	compute_stats(worst_latencies_ns, g_iterations, &avg, &max, &min, &stddev);
	printf("Results (from a stop):\n");
	printf("Max:\t\t%.2f us\n", ((float)max) / 1000.0);
	printf("Min:\t\t%.2f us\n", ((float)min) / 1000.0);
	printf("Avg:\t\t%.2f us\n", avg / 1000.0);
	printf("Stddev:\t\t%.2f us\n", stddev / 1000.0);

	putchar('\n');

	compute_stats(worst_latencies_from_first_ns, g_iterations, &avg, &max, &min, &stddev);
	printf("Results (relative to first thread):\n");
	printf("Max:\t\t%.2f us\n", ((float)max) / 1000.0);
	printf("Min:\t\t%.2f us\n", ((float)min) / 1000.0);
	printf("Avg:\t\t%.2f us\n", avg / 1000.0);
	printf("Stddev:\t\t%.2f us\n", stddev / 1000.0);

#if 0
	for (i = 0; i < g_iterations; i++) {
		printf("Iteration %d: %f us\n", i, worst_latencies_ns[i] / 1000.0);
	}
#endif 

	return 0;
fail:
	return 1;
}

/*
 * WARNING: This is SPI specifically intended for use by launchd to start UI
 * apps. We use it here for a test tool only to opt into QoS using the same
 * policies. Do not use this outside xnu or libxpc/launchd.
 */
void
selfexec_with_apptype(int argc, char *argv[])
{
	int ret;
	posix_spawnattr_t attr;
	extern char **environ;
	char *new_argv[argc + 1 + 1 /* NULL */];
	int i;
	char prog[PATH_MAX];
	uint32_t prog_size = PATH_MAX;

	ret = _NSGetExecutablePath(prog, &prog_size);
	if (ret != 0) err(1, "_NSGetExecutablePath");

	for (i=0; i < argc; i++) {
		new_argv[i] = argv[i];
	}

	new_argv[i]   = "-switched_apptype";
	new_argv[i+1] = NULL;

	ret = posix_spawnattr_init(&attr);
	if (ret != 0) errc(1, ret, "posix_spawnattr_init");

	ret = posix_spawnattr_setflags(&attr, POSIX_SPAWN_SETEXEC);
	if (ret != 0) errc(1, ret, "posix_spawnattr_setflags");

	ret = posix_spawnattr_setprocesstype_np(&attr, POSIX_SPAWN_PROC_TYPE_APP_DEFAULT);
	if (ret != 0) errc(1, ret, "posix_spawnattr_setprocesstype_np");

	ret = posix_spawn(NULL, prog, NULL, &attr, new_argv, environ);
	if (ret != 0) errc(1, ret, "posix_spawn");
}
Commit	Line	Data
6d2010ae A	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>
fe8ab488	32	#include <sys/param.h>
a1c7dba1	33	#include <sys/kdebug.h>
6d2010ae A	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>
fe8ab488	41	#include <err.h>
6d2010ae A	42	#include <string.h>
6d2010ae A	43
fe8ab488 A	44	#include <spawn.h>
	45	#include <spawn_private.h>
	46	#include <sys/spawn_internal.h>
	47	#include <mach-o/dyld.h>
	48
6d2010ae A	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();
39236c6e	74	int thread_setup(int my_id);
6d2010ae A	75	my_policy_type_t parse_thread_policy(const char *str);
6d2010ae A	76	int thread_finish_iteration();
fe8ab488	77	void selfexec_with_apptype(int argc, char *argv[]);
6d2010ae A	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;
39236c6e	90	boolean_t g_do_affinity = FALSE;
6d2010ae A	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
39236c6e	156	thread_setup(int my_id)
6d2010ae A	157	{
	158	int res;
	159
	160	switch (g_policy) {
	161	case MY_POLICY_TIMESHARE:
	162	{
fe8ab488 A	163	res = KERN_SUCCESS;
fe8ab488 A	164	break;
6d2010ae A	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
39236c6e A	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
6d2010ae A	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 {
39236c6e	252	#ifndef MIMIC_DIGI_LEAD_TIME
6d2010ae A	253	if (g_do_spin) {
	254	while (g_done_threads < g_numthreads) {
	255	y = y + 1.5 + x;
	256	x = sqrt(y);
	257	}
	258	}
39236c6e	259	#endif
6d2010ae A	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 */
39236c6e	278	thread_setup(my_id);
6d2010ae A	279
	280	/* Tell main thread when everyone has set up */
	281	new = OSAtomicIncrement32(&g_done_threads);
fe8ab488	282	semaphore_signal(g_main_sem);
6d2010ae A	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	{
39236c6e	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");
6d2010ae A	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;
fe8ab488	423	boolean_t seen_apptype = FALSE;
6d2010ae A	424
	425	srand(time(NULL));
	426
fe8ab488	427	if (argc < 5 \|\| argc > 10) {
6d2010ae A	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);
39236c6e A	453	} else if (strcmp(argv[i], "-affinity") == 0) {
39236c6e A	454	g_do_affinity = TRUE;
fe8ab488 A	455	} else if (strcmp(argv[i], "-switched_apptype") == 0) {
fe8ab488 A	456	seen_apptype = TRUE;
6d2010ae A	457	} else {
	458	print_usage();
	459	goto fail;
	460	}
	461	}
	462
fe8ab488 A	463	if (!seen_apptype) {
	464	selfexec_with_apptype(argc, argv);
	465	}
	466
6d2010ae A	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
fe8ab488 A	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
6d2010ae	532	/* Let everyone get settled */
fe8ab488 A	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);
6d2010ae A	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
a1c7dba1 A	591	_tmp = kdebug_trace(0xeeeee0 \| DBG_FUNC_NONE,
	592	worst_latencies_from_first_ns[i] >> 32,
	593	worst_latencies_from_first_ns[i] & 0xFFFFFFFF,
	594	traceworthy_latency_ns >> 32,
	595	traceworthy_latency_ns & 0xFFFFFFFF);
6d2010ae A	596	}
	597
	598	/* Let worker threads get back to sleep... */
	599	usleep(g_numthreads * 10);
	600	}
	601
	602	/* Rejoin threads */
	603	last_end = 0;
	604	for (i = 0; i < g_numthreads; i++) {
	605	res = pthread_join(threads[i], NULL);
	606	assert(res == 0, fail);
	607	}
	608
	609	compute_stats(worst_latencies_ns, g_iterations, &avg, &max, &min, &stddev);
	610	printf("Results (from a stop):\n");
	611	printf("Max:\t\t%.2f us\n", ((float)max) / 1000.0);
	612	printf("Min:\t\t%.2f us\n", ((float)min) / 1000.0);
	613	printf("Avg:\t\t%.2f us\n", avg / 1000.0);
	614	printf("Stddev:\t\t%.2f us\n", stddev / 1000.0);
	615
	616	putchar('\n');
	617
	618	compute_stats(worst_latencies_from_first_ns, g_iterations, &avg, &max, &min, &stddev);
	619	printf("Results (relative to first thread):\n");
	620	printf("Max:\t\t%.2f us\n", ((float)max) / 1000.0);
	621	printf("Min:\t\t%.2f us\n", ((float)min) / 1000.0);
	622	printf("Avg:\t\t%.2f us\n", avg / 1000.0);
	623	printf("Stddev:\t\t%.2f us\n", stddev / 1000.0);
	624
	625	#if 0
	626	for (i = 0; i < g_iterations; i++) {
	627	printf("Iteration %d: %f us\n", i, worst_latencies_ns[i] / 1000.0);
	628	}
	629	#endif
	630
	631	return 0;
	632	fail:
	633	return 1;
	634	}
fe8ab488 A	635
	636	/*
	637	* WARNING: This is SPI specifically intended for use by launchd to start UI
	638	* apps. We use it here for a test tool only to opt into QoS using the same
	639	* policies. Do not use this outside xnu or libxpc/launchd.
	640	*/
	641	void
	642	selfexec_with_apptype(int argc, char *argv[])
	643	{
	644	int ret;
	645	posix_spawnattr_t attr;
	646	extern char **environ;
	647	char new_argv[argc + 1 + 1 / NULL */];
	648	int i;
	649	char prog[PATH_MAX];
a1c7dba1	650	uint32_t prog_size = PATH_MAX;
fe8ab488 A	651
	652	ret = _NSGetExecutablePath(prog, &prog_size);
	653	if (ret != 0) err(1, "_NSGetExecutablePath");
	654
	655	for (i=0; i < argc; i++) {
	656	new_argv[i] = argv[i];
	657	}
	658
	659	new_argv[i] = "-switched_apptype";
	660	new_argv[i+1] = NULL;
	661
	662	ret = posix_spawnattr_init(&attr);
	663	if (ret != 0) errc(1, ret, "posix_spawnattr_init");
	664
	665	ret = posix_spawnattr_setflags(&attr, POSIX_SPAWN_SETEXEC);
	666	if (ret != 0) errc(1, ret, "posix_spawnattr_setflags");
	667
	668	ret = posix_spawnattr_setprocesstype_np(&attr, POSIX_SPAWN_PROC_TYPE_APP_DEFAULT);
	669	if (ret != 0) errc(1, ret, "posix_spawnattr_setprocesstype_np");
	670
	671	ret = posix_spawn(NULL, prog, NULL, &attr, new_argv, environ);
	672	if (ret != 0) errc(1, ret, "posix_spawn");
	673	}