[apple/xnu.git] / osfmk / kern / sched_proto.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 <mach/mach_types.h>
#include <mach/machine.h>
#include <mach/policy.h>
#include <mach/sync_policy.h>
#include <mach/thread_act.h>

#include <machine/machine_routines.h>
#include <machine/sched_param.h>
#include <machine/machine_cpu.h>

#include <kern/kern_types.h>
#include <kern/clock.h>
#include <kern/counters.h>
#include <kern/cpu_number.h>
#include <kern/cpu_data.h>
#include <kern/debug.h>
#include <kern/lock.h>
#include <kern/macro_help.h>
#include <kern/machine.h>
#include <kern/misc_protos.h>
#include <kern/processor.h>
#include <kern/queue.h>
#include <kern/sched.h>
#include <kern/sched_prim.h>
#include <kern/syscall_subr.h>
#include <kern/task.h>
#include <kern/thread.h>
#include <kern/wait_queue.h>

#include <vm/pmap.h>
#include <vm/vm_kern.h>
#include <vm/vm_map.h>

#include <mach/sdt.h>

#include <sys/kdebug.h>

static void
sched_proto_init(void);

static void
sched_proto_timebase_init(void);

static void
sched_proto_processor_init(processor_t processor);

static void
sched_proto_pset_init(processor_set_t pset);

static void
sched_proto_maintenance_continuation(void);

static thread_t
sched_proto_choose_thread(processor_t		processor,
							 int				priority);

static thread_t
sched_proto_steal_thread(processor_set_t		pset);

static void
sched_proto_compute_priority(thread_t	thread,
							 boolean_t			override_depress);

static processor_t
sched_proto_choose_processor(	processor_set_t		pset,
								processor_t			processor,
								thread_t			thread);


static boolean_t
sched_proto_processor_enqueue(
							 processor_t			processor,
							 thread_t			thread,
							 integer_t			options);

static void
sched_proto_processor_queue_shutdown(
									 processor_t			processor);

static boolean_t
sched_proto_processor_queue_remove(
						    processor_t			processor,
							thread_t		thread);

static boolean_t
sched_proto_processor_queue_empty(processor_t		processor);

static boolean_t
sched_proto_processor_queue_has_priority(processor_t		processor,
										 int				priority,
										 boolean_t		gte);

static boolean_t
sched_proto_priority_is_urgent(int priority);

static ast_t
sched_proto_processor_csw_check(processor_t processor);

static uint32_t
sched_proto_initial_quantum_size(thread_t thread);

static sched_mode_t
sched_proto_initial_thread_sched_mode(task_t parent_task);

static boolean_t
sched_proto_supports_timeshare_mode(void);

static boolean_t
sched_proto_can_update_priority(thread_t	thread);

static void
sched_proto_update_priority(thread_t	thread);

static void
sched_proto_lightweight_update_priority(thread_t	thread);

static void
sched_proto_quantum_expire(thread_t	thread);

static boolean_t
sched_proto_should_current_thread_rechoose_processor(processor_t			processor);

static int
sched_proto_processor_runq_count(processor_t   processor);

static uint64_t
sched_proto_processor_runq_stats_count_sum(processor_t   processor);

const struct sched_dispatch_table sched_proto_dispatch = {
	sched_proto_init,
	sched_proto_timebase_init,
	sched_proto_processor_init,
	sched_proto_pset_init,
	sched_proto_maintenance_continuation,
	sched_proto_choose_thread,
	sched_proto_steal_thread,
	sched_proto_compute_priority,
	sched_proto_choose_processor,
	sched_proto_processor_enqueue,
	sched_proto_processor_queue_shutdown,
	sched_proto_processor_queue_remove,
	sched_proto_processor_queue_empty,
	sched_proto_priority_is_urgent,
	sched_proto_processor_csw_check,
	sched_proto_processor_queue_has_priority,
	sched_proto_initial_quantum_size,
	sched_proto_initial_thread_sched_mode,
	sched_proto_supports_timeshare_mode,
	sched_proto_can_update_priority,
	sched_proto_update_priority,
	sched_proto_lightweight_update_priority,
	sched_proto_quantum_expire,
	sched_proto_should_current_thread_rechoose_processor,
	sched_proto_processor_runq_count,
	sched_proto_processor_runq_stats_count_sum,
	sched_traditional_fairshare_init,
	sched_traditional_fairshare_runq_count,
	sched_traditional_fairshare_runq_stats_count_sum,
	sched_traditional_fairshare_enqueue,
	sched_traditional_fairshare_dequeue,
	sched_traditional_fairshare_queue_remove,
	TRUE /* direct_dispatch_to_idle_processors */
};

static struct run_queue	*global_runq;
static struct run_queue	global_runq_storage;

#define GLOBAL_RUNQ		((processor_t)-2)
decl_simple_lock_data(static,global_runq_lock);

extern int	max_unsafe_quanta;

static uint32_t proto_quantum_us;
static uint32_t proto_quantum;

static uint32_t	runqueue_generation;

static processor_t proto_processor;

static uint64_t			sched_proto_tick_deadline;
static uint32_t			sched_proto_tick;

static void
sched_proto_init(void)
{
	proto_quantum_us = 10*1000;
	
	printf("standard proto timeslicing quantum is %d us\n", proto_quantum_us);

	simple_lock_init(&global_runq_lock, 0);
	global_runq = &global_runq_storage;
	run_queue_init(global_runq);
	runqueue_generation = 0;
	
	proto_processor = master_processor;
}

static void
sched_proto_timebase_init(void)
{
	uint64_t	abstime;

	/* standard timeslicing quantum */
	clock_interval_to_absolutetime_interval(
											proto_quantum_us, NSEC_PER_USEC, &abstime);
	assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
	proto_quantum = (uint32_t)abstime;
	
	thread_depress_time = 1 * proto_quantum;
	default_timeshare_computation = proto_quantum / 2;
	default_timeshare_constraint = proto_quantum;
	
	max_unsafe_computation = max_unsafe_quanta * proto_quantum;
	sched_safe_duration = 2 * max_unsafe_quanta * proto_quantum;

}

static void
sched_proto_processor_init(processor_t processor __unused)
{
	/* No per-processor state */
}

static void
sched_proto_pset_init(processor_set_t pset __unused)
{
}

static void
sched_proto_maintenance_continuation(void)
{
	uint64_t			abstime = mach_absolute_time();
	
	sched_proto_tick++;
	
	/* Every 8 seconds, switch to another processor */
	if ((sched_proto_tick & 0x7) == 0) {
		processor_t new_processor;
		
		new_processor = proto_processor->processor_list;
		if (new_processor == PROCESSOR_NULL)
			proto_processor = master_processor;
		else
			proto_processor = new_processor;
	}
		
	
	/*
	 *  Compute various averages.
	 */
	compute_averages();
	
	if (sched_proto_tick_deadline == 0)
		sched_proto_tick_deadline = abstime;
	
	clock_deadline_for_periodic_event(sched_one_second_interval, abstime,
						&sched_proto_tick_deadline);
	
	assert_wait_deadline((event_t)sched_proto_maintenance_continuation, THREAD_UNINT, sched_proto_tick_deadline);
	thread_block((thread_continue_t)sched_proto_maintenance_continuation);
	/*NOTREACHED*/
}

static thread_t
sched_proto_choose_thread(processor_t		processor,
						  int				priority)
{
	run_queue_t		rq = global_runq;
	queue_t			queue;
	int				pri, count;
	thread_t		thread;
	
	
	simple_lock(&global_runq_lock);
	
	queue = rq->queues + rq->highq;
	pri = rq->highq;
	count = rq->count;
	
	/*
	 * Since we don't depress priorities, a high priority thread
	 * may get selected over and over again. Put a runqueue
	 * generation number in the thread structure so that we
	 * can ensure that we've cycled through all runnable tasks
	 * before coming back to a high priority thread. This isn't
	 * perfect, especially if the number of runnable threads always
	 * stays high, but is a workable approximation
	 */
	 
	while (count > 0 && pri >= priority) {
		thread = (thread_t)queue_first(queue);
		while (!queue_end(queue, (queue_entry_t)thread)) {
			if ((thread->bound_processor == PROCESSOR_NULL ||
				thread->bound_processor == processor) &&
				runqueue_generation != thread->runqueue_generation) {
				remqueue((queue_entry_t)thread);
				
				thread->runq = PROCESSOR_NULL;
				thread->runqueue_generation = runqueue_generation;
				SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
				rq->count--;
				if (queue_empty(queue)) {
					if (pri != IDLEPRI)
						clrbit(MAXPRI - pri, rq->bitmap);
					rq->highq = MAXPRI - ffsbit(rq->bitmap);
				}
				
				simple_unlock(&global_runq_lock);
				return (thread);
			}
			count--;
			
			thread = (thread_t)queue_next((queue_entry_t)thread);
		}
		
		queue--; pri--;
	}
	
	runqueue_generation++;
	
	simple_unlock(&global_runq_lock);
	return (THREAD_NULL);
}

static thread_t
sched_proto_steal_thread(processor_set_t		pset)
{
	pset_unlock(pset);
	
	return (THREAD_NULL);
	
}

static void
sched_proto_compute_priority(thread_t	thread,
							 boolean_t			override_depress __unused)
{
	set_sched_pri(thread, thread->priority);
}

static processor_t
sched_proto_choose_processor(	processor_set_t		pset,
							 processor_t			processor,
							 thread_t			thread __unused)
{
	processor = proto_processor;
	
	/*
	 *	Check that the correct processor set is
	 *	returned locked.
	 */
	if (pset != processor->processor_set) {
		pset_unlock(pset);
		
		pset = processor->processor_set;
		pset_lock(pset);
	}
	
	return (processor);
}

static boolean_t
sched_proto_processor_enqueue(
							 processor_t			processor __unused,
							 thread_t			thread,
							 integer_t			options)
{
	run_queue_t		rq = global_runq;
	boolean_t		result;
	
	simple_lock(&global_runq_lock);
	result = run_queue_enqueue(rq, thread, options);
	thread->runq = GLOBAL_RUNQ;
	simple_unlock(&global_runq_lock);
	
	return (result);
}

static void
sched_proto_processor_queue_shutdown(
									 processor_t			processor)
{
	/* With a global runqueue, just stop choosing this processor */
	(void)processor;
}

static boolean_t
sched_proto_processor_queue_remove(
								processor_t			processor,
								thread_t		thread)
{
	void *			rqlock;
	run_queue_t		rq;
	
	rqlock = &global_runq_lock;
	rq = global_runq;
	
	simple_lock(rqlock);
	if (processor == thread->runq) {
		/*
		 *	Thread is on a run queue and we have a lock on
		 *	that run queue.
		 */
		remqueue((queue_entry_t)thread);
		SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
		rq->count--;
		if (SCHED(priority_is_urgent)(thread->sched_pri)) {
			rq->urgency--; assert(rq->urgency >= 0);
		}
		
		if (queue_empty(rq->queues + thread->sched_pri)) {
			/* update run queue status */
			if (thread->sched_pri != IDLEPRI)
				clrbit(MAXPRI - thread->sched_pri, rq->bitmap);
			rq->highq = MAXPRI - ffsbit(rq->bitmap);
		}
		
		thread->runq = PROCESSOR_NULL;
	}
	else {
		/*
		 *	The thread left the run queue before we could
		 * 	lock the run queue.
		 */
		assert(thread->runq == PROCESSOR_NULL);
		processor = PROCESSOR_NULL;
	}
	
	simple_unlock(rqlock);
	
	return (processor != PROCESSOR_NULL);
}

static boolean_t
sched_proto_processor_queue_empty(processor_t		processor __unused)
{
	boolean_t result;
	
	result = (global_runq->count == 0);
	
	return result;
}

static boolean_t
sched_proto_processor_queue_has_priority(processor_t		processor __unused,
										 int				priority,
										 boolean_t		gte)
{
	boolean_t result;
	
	simple_lock(&global_runq_lock);

	if (gte)
		result = global_runq->highq >= priority;
	else
		result = global_runq->highq >= priority;

	simple_unlock(&global_runq_lock);
	
	return result;
}

/* Implement sched_preempt_pri in code */
static boolean_t
sched_proto_priority_is_urgent(int priority)
{
	if (priority <= BASEPRI_FOREGROUND)
		return FALSE;
	
	if (priority < MINPRI_KERNEL)
		return TRUE;

	if (priority >= BASEPRI_PREEMPT)
		return TRUE;
	
	return FALSE;
}

static ast_t
sched_proto_processor_csw_check(processor_t processor __unused)
{
	run_queue_t		runq;
	int				count, urgency;
	
	runq = global_runq;
	count = runq->count;
	urgency = runq->urgency;
	
	if (count > 0) {
		if (urgency > 0)
			return (AST_PREEMPT | AST_URGENT);
		
		return AST_PREEMPT;
	}
	
	return AST_NONE;
}

static uint32_t
sched_proto_initial_quantum_size(thread_t thread __unused)
{
	return proto_quantum;
}

static sched_mode_t
sched_proto_initial_thread_sched_mode(task_t parent_task)
{
	if (parent_task == kernel_task)
		return TH_MODE_FIXED;
	else
		return TH_MODE_TIMESHARE;	
}

static boolean_t
sched_proto_supports_timeshare_mode(void)
{
	return TRUE;
}

static boolean_t
sched_proto_can_update_priority(thread_t	thread __unused)
{
	return FALSE;
}

static void
sched_proto_update_priority(thread_t	thread __unused)
{
	
}

static void
sched_proto_lightweight_update_priority(thread_t	thread __unused)
{
	
}

static void
sched_proto_quantum_expire(thread_t	thread __unused)
{
	
}

static boolean_t
sched_proto_should_current_thread_rechoose_processor(processor_t			processor)
{
	return (proto_processor != processor);
}

static int
sched_proto_processor_runq_count(processor_t   processor)
{
	if (master_processor == processor) {
		return global_runq->count;
	} else {
		return 0;
	}	
}

static uint64_t
sched_proto_processor_runq_stats_count_sum(processor_t   processor)
{
	if (master_processor == processor) {
		return global_runq->runq_stats.count_sum;
	} else {
		return 0ULL;
	}
}
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
	29	#include <mach/mach_types.h>
	30	#include <mach/machine.h>
	31	#include <mach/policy.h>
	32	#include <mach/sync_policy.h>
	33	#include <mach/thread_act.h>
	34
	35	#include <machine/machine_routines.h>
	36	#include <machine/sched_param.h>
	37	#include <machine/machine_cpu.h>
	38
	39	#include <kern/kern_types.h>
	40	#include <kern/clock.h>
	41	#include <kern/counters.h>
	42	#include <kern/cpu_number.h>
	43	#include <kern/cpu_data.h>
	44	#include <kern/debug.h>
	45	#include <kern/lock.h>
	46	#include <kern/macro_help.h>
	47	#include <kern/machine.h>
	48	#include <kern/misc_protos.h>
	49	#include <kern/processor.h>
	50	#include <kern/queue.h>
	51	#include <kern/sched.h>
	52	#include <kern/sched_prim.h>
	53	#include <kern/syscall_subr.h>
	54	#include <kern/task.h>
	55	#include <kern/thread.h>
	56	#include <kern/wait_queue.h>
	57
	58	#include <vm/pmap.h>
	59	#include <vm/vm_kern.h>
	60	#include <vm/vm_map.h>
	61
	62	#include <mach/sdt.h>
	63
	64	#include <sys/kdebug.h>
65
66	static void
67	sched_proto_init(void);
68
69	static void
70	sched_proto_timebase_init(void);
71
72	static void
73	sched_proto_processor_init(processor_t processor);
74
75	static void
76	sched_proto_pset_init(processor_set_t pset);
77
78	static void
79	sched_proto_maintenance_continuation(void);
80
81	static thread_t
82	sched_proto_choose_thread(processor_t processor,
83	int priority);
84
85	static thread_t
86	sched_proto_steal_thread(processor_set_t pset);
87
88	static void
89	sched_proto_compute_priority(thread_t thread,
90	boolean_t override_depress);
91
92	static processor_t
93	sched_proto_choose_processor( processor_set_t pset,
94	processor_t processor,
95	thread_t thread);
96
97
98	static boolean_t
99	sched_proto_processor_enqueue(
100	processor_t processor,
101	thread_t thread,
102	integer_t options);
103
104	static void
105	sched_proto_processor_queue_shutdown(
106	processor_t processor);
107
108	static boolean_t
109	sched_proto_processor_queue_remove(
110	processor_t processor,
111	thread_t thread);
112
113	static boolean_t
114	sched_proto_processor_queue_empty(processor_t processor);
115
116	static boolean_t
117	sched_proto_processor_queue_has_priority(processor_t processor,
118	int priority,
119	boolean_t gte);
120
121	static boolean_t
122	sched_proto_priority_is_urgent(int priority);
123
124	static ast_t
125	sched_proto_processor_csw_check(processor_t processor);
126
127	static uint32_t
128	sched_proto_initial_quantum_size(thread_t thread);
129
130	static sched_mode_t
131	sched_proto_initial_thread_sched_mode(task_t parent_task);
132
133	static boolean_t
134	sched_proto_supports_timeshare_mode(void);
135
136	static boolean_t
137	sched_proto_can_update_priority(thread_t thread);
138
139	static void
140	sched_proto_update_priority(thread_t thread);
141
142	static void
143	sched_proto_lightweight_update_priority(thread_t thread);
144
145	static void
146	sched_proto_quantum_expire(thread_t thread);
147
148	static boolean_t
149	sched_proto_should_current_thread_rechoose_processor(processor_t processor);
150
151	static int
152	sched_proto_processor_runq_count(processor_t processor);
153
154	static uint64_t
155	sched_proto_processor_runq_stats_count_sum(processor_t processor);
156
157	const struct sched_dispatch_table sched_proto_dispatch = {
158	sched_proto_init,
159	sched_proto_timebase_init,
160	sched_proto_processor_init,
161	sched_proto_pset_init,
162	sched_proto_maintenance_continuation,
163	sched_proto_choose_thread,
164	sched_proto_steal_thread,
165	sched_proto_compute_priority,
166	sched_proto_choose_processor,
167	sched_proto_processor_enqueue,
168	sched_proto_processor_queue_shutdown,
169	sched_proto_processor_queue_remove,
170	sched_proto_processor_queue_empty,
171	sched_proto_priority_is_urgent,
172	sched_proto_processor_csw_check,
173	sched_proto_processor_queue_has_priority,
174	sched_proto_initial_quantum_size,
175	sched_proto_initial_thread_sched_mode,
176	sched_proto_supports_timeshare_mode,
177	sched_proto_can_update_priority,
178	sched_proto_update_priority,
179	sched_proto_lightweight_update_priority,
180	sched_proto_quantum_expire,
181	sched_proto_should_current_thread_rechoose_processor,
182	sched_proto_processor_runq_count,
183	sched_proto_processor_runq_stats_count_sum,
184	sched_traditional_fairshare_init,
185	sched_traditional_fairshare_runq_count,
186	sched_traditional_fairshare_runq_stats_count_sum,
187	sched_traditional_fairshare_enqueue,
188	sched_traditional_fairshare_dequeue,
189	sched_traditional_fairshare_queue_remove,
190	TRUE /* direct_dispatch_to_idle_processors */
191	};
192
193	static struct run_queue *global_runq;
194	static struct run_queue global_runq_storage;
195
196	#define GLOBAL_RUNQ ((processor_t)-2)
197	decl_simple_lock_data(static,global_runq_lock);
198
199	extern int max_unsafe_quanta;
200
201	static uint32_t proto_quantum_us;
202	static uint32_t proto_quantum;
203
204	static uint32_t runqueue_generation;
205
206	static processor_t proto_processor;
207
208	static uint64_t sched_proto_tick_deadline;
209	static uint32_t sched_proto_tick;
210
211	static void
212	sched_proto_init(void)
213	{
214	proto_quantum_us = 10*1000;
215
216	printf("standard proto timeslicing quantum is %d us\n", proto_quantum_us);
217
218	simple_lock_init(&global_runq_lock, 0);
219	global_runq = &global_runq_storage;
220	run_queue_init(global_runq);
221	runqueue_generation = 0;
222
223	proto_processor = master_processor;
224	}
225
226	static void
227	sched_proto_timebase_init(void)
228	{
229	uint64_t abstime;
230
231	/* standard timeslicing quantum */
232	clock_interval_to_absolutetime_interval(
233	proto_quantum_us, NSEC_PER_USEC, &abstime);
234	assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
235	proto_quantum = (uint32_t)abstime;
236
237	thread_depress_time = 1 * proto_quantum;
238	default_timeshare_computation = proto_quantum / 2;
239	default_timeshare_constraint = proto_quantum;
240
241	max_unsafe_computation = max_unsafe_quanta * proto_quantum;
242	sched_safe_duration = 2 * max_unsafe_quanta * proto_quantum;
243
244	}
245
246	static void
247	sched_proto_processor_init(processor_t processor __unused)
248	{
249	/* No per-processor state */
250	}
251
252	static void
253	sched_proto_pset_init(processor_set_t pset __unused)
254	{
255	}
256
257	static void
258	sched_proto_maintenance_continuation(void)
259	{
260	uint64_t abstime = mach_absolute_time();
261
262	sched_proto_tick++;
263
264	/* Every 8 seconds, switch to another processor */
265	if ((sched_proto_tick & 0x7) == 0) {
266	processor_t new_processor;
267
268	new_processor = proto_processor->processor_list;
269	if (new_processor == PROCESSOR_NULL)
270	proto_processor = master_processor;
271	else
272	proto_processor = new_processor;
273	}
274
275
276	/*
277	* Compute various averages.
278	*/
279	compute_averages();
280
281	if (sched_proto_tick_deadline == 0)
282	sched_proto_tick_deadline = abstime;
283
284	clock_deadline_for_periodic_event(sched_one_second_interval, abstime,
285	&sched_proto_tick_deadline);
286
287	assert_wait_deadline((event_t)sched_proto_maintenance_continuation, THREAD_UNINT, sched_proto_tick_deadline);
288	thread_block((thread_continue_t)sched_proto_maintenance_continuation);
289	/NOTREACHED/
290	}
291
292	static thread_t
293	sched_proto_choose_thread(processor_t processor,
294	int priority)
295	{
296	run_queue_t rq = global_runq;
297	queue_t queue;
298	int pri, count;
299	thread_t thread;
300
301
302	simple_lock(&global_runq_lock);
303
304	queue = rq->queues + rq->highq;
305	pri = rq->highq;
306	count = rq->count;
307
308	/*
309	* Since we don't depress priorities, a high priority thread
310	* may get selected over and over again. Put a runqueue
311	* generation number in the thread structure so that we
312	* can ensure that we've cycled through all runnable tasks
313	* before coming back to a high priority thread. This isn't
314	* perfect, especially if the number of runnable threads always
315	* stays high, but is a workable approximation
316	*/
317
318	while (count > 0 && pri >= priority) {
319	thread = (thread_t)queue_first(queue);
320	while (!queue_end(queue, (queue_entry_t)thread)) {
321	if ((thread->bound_processor == PROCESSOR_NULL \|\|
322	thread->bound_processor == processor) &&
323	runqueue_generation != thread->runqueue_generation) {
324	remqueue((queue_entry_t)thread);
325
326	thread->runq = PROCESSOR_NULL;
327	thread->runqueue_generation = runqueue_generation;
328	SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
329	rq->count--;
330	if (queue_empty(queue)) {
331	if (pri != IDLEPRI)
332	clrbit(MAXPRI - pri, rq->bitmap);
333	rq->highq = MAXPRI - ffsbit(rq->bitmap);
334	}
335
336	simple_unlock(&global_runq_lock);
337	return (thread);
338	}
339	count--;
340
341	thread = (thread_t)queue_next((queue_entry_t)thread);
342	}
343
344	queue--; pri--;
345	}
346
347	runqueue_generation++;
348
349	simple_unlock(&global_runq_lock);
350	return (THREAD_NULL);
351	}
352
353	static thread_t
354	sched_proto_steal_thread(processor_set_t pset)
355	{
356	pset_unlock(pset);
357
358	return (THREAD_NULL);
359
360	}
361
362	static void
363	sched_proto_compute_priority(thread_t thread,
364	boolean_t override_depress __unused)
365	{
366	set_sched_pri(thread, thread->priority);
367	}
368
369	static processor_t
370	sched_proto_choose_processor( processor_set_t pset,
371	processor_t processor,
372	thread_t thread __unused)
373	{
374	processor = proto_processor;
375
376	/*
377	* Check that the correct processor set is
378	* returned locked.
379	*/
380	if (pset != processor->processor_set) {
381	pset_unlock(pset);
382
383	pset = processor->processor_set;
384	pset_lock(pset);
385	}
386
387	return (processor);
388	}
389
390	static boolean_t
391	sched_proto_processor_enqueue(
392	processor_t processor __unused,
393	thread_t thread,
394	integer_t options)
395	{
396	run_queue_t rq = global_runq;
397	boolean_t result;
398
399	simple_lock(&global_runq_lock);
400	result = run_queue_enqueue(rq, thread, options);
401	thread->runq = GLOBAL_RUNQ;
402	simple_unlock(&global_runq_lock);
403
404	return (result);
405	}
406
407	static void
408	sched_proto_processor_queue_shutdown(
409	processor_t processor)
410	{
411	/* With a global runqueue, just stop choosing this processor */
412	(void)processor;
413	}
414
415	static boolean_t
416	sched_proto_processor_queue_remove(
417	processor_t processor,
418	thread_t thread)
419	{
420	void * rqlock;
421	run_queue_t rq;
422
423	rqlock = &global_runq_lock;
424	rq = global_runq;
425
426	simple_lock(rqlock);
427	if (processor == thread->runq) {
428	/*
429	* Thread is on a run queue and we have a lock on
430	* that run queue.
431	*/
432	remqueue((queue_entry_t)thread);
433	SCHED_STATS_RUNQ_CHANGE(&rq->runq_stats, rq->count);
434	rq->count--;
435	if (SCHED(priority_is_urgent)(thread->sched_pri)) {
436	rq->urgency--; assert(rq->urgency >= 0);
437	}
438
439	if (queue_empty(rq->queues + thread->sched_pri)) {
440	/* update run queue status */
441	if (thread->sched_pri != IDLEPRI)
442	clrbit(MAXPRI - thread->sched_pri, rq->bitmap);
443	rq->highq = MAXPRI - ffsbit(rq->bitmap);
444	}
445
446	thread->runq = PROCESSOR_NULL;
447	}
448	else {
449	/*
450	* The thread left the run queue before we could
451	* lock the run queue.
452	*/
453	assert(thread->runq == PROCESSOR_NULL);
454	processor = PROCESSOR_NULL;
455	}
456
457	simple_unlock(rqlock);
458
459	return (processor != PROCESSOR_NULL);
460	}
461
462	static boolean_t
463	sched_proto_processor_queue_empty(processor_t processor __unused)
464	{
465	boolean_t result;
466
467	result = (global_runq->count == 0);
468
469	return result;
470	}
471
472	static boolean_t
473	sched_proto_processor_queue_has_priority(processor_t processor __unused,
474	int priority,
475	boolean_t gte)
476	{
477	boolean_t result;
478
479	simple_lock(&global_runq_lock);
480
481	if (gte)
482	result = global_runq->highq >= priority;
483	else
484	result = global_runq->highq >= priority;
485
486	simple_unlock(&global_runq_lock);
487
488	return result;
489	}
490
491	/* Implement sched_preempt_pri in code */
492	static boolean_t
493	sched_proto_priority_is_urgent(int priority)
494	{
495	if (priority <= BASEPRI_FOREGROUND)
496	return FALSE;
497
498	if (priority < MINPRI_KERNEL)
499	return TRUE;
500
501	if (priority >= BASEPRI_PREEMPT)
502	return TRUE;
503
504	return FALSE;
505	}
506
507	static ast_t
508	sched_proto_processor_csw_check(processor_t processor __unused)
509	{
510	run_queue_t runq;
511	int count, urgency;
512
513	runq = global_runq;
514	count = runq->count;
515	urgency = runq->urgency;
516
517	if (count > 0) {
518	if (urgency > 0)
519	return (AST_PREEMPT \| AST_URGENT);
520
521	return AST_PREEMPT;
522	}
523
524	return AST_NONE;
525	}
526
527	static uint32_t
528	sched_proto_initial_quantum_size(thread_t thread __unused)
529	{
530	return proto_quantum;
531	}
532
533	static sched_mode_t
534	sched_proto_initial_thread_sched_mode(task_t parent_task)
535	{
536	if (parent_task == kernel_task)
537	return TH_MODE_FIXED;
538	else
539	return TH_MODE_TIMESHARE;
540	}
541
542	static boolean_t
543	sched_proto_supports_timeshare_mode(void)
544	{
545	return TRUE;
546	}
547
548	static boolean_t
549	sched_proto_can_update_priority(thread_t thread __unused)
550	{
551	return FALSE;
552	}
553
554	static void
555	sched_proto_update_priority(thread_t thread __unused)
556	{
557
558	}
559
560	static void
561	sched_proto_lightweight_update_priority(thread_t thread __unused)
562	{
563
564	}
565
566	static void
567	sched_proto_quantum_expire(thread_t thread __unused)
568	{
569
570	}
571
572	static boolean_t
573	sched_proto_should_current_thread_rechoose_processor(processor_t processor)
574	{
575	return (proto_processor != processor);
576	}
577
578	static int
579	sched_proto_processor_runq_count(processor_t processor)
580	{
581	if (master_processor == processor) {
582	return global_runq->count;
583	} else {
584	return 0;
585	}
586	}
587
588	static uint64_t
589	sched_proto_processor_runq_stats_count_sum(processor_t processor)
590	{
591	if (master_processor == processor) {
592	return global_runq->runq_stats.count_sum;
593	} else {
594	return 0ULL;
595	}
596	}
597