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
66static void
67sched_proto_init(void);
68
69static void
70sched_proto_timebase_init(void);
71
72static void
73sched_proto_processor_init(processor_t processor);
74
75static void
76sched_proto_pset_init(processor_set_t pset);
77
78static void
79sched_proto_maintenance_continuation(void);
80
81static thread_t
82sched_proto_choose_thread(processor_t		processor,
83							 int				priority);
84
85static thread_t
86sched_proto_steal_thread(processor_set_t		pset);
87
88static void
89sched_proto_compute_priority(thread_t	thread,
90							 boolean_t			override_depress);
91
92static processor_t
93sched_proto_choose_processor(	processor_set_t		pset,
94								processor_t			processor,
95								thread_t			thread);
96
97
98static boolean_t
99sched_proto_processor_enqueue(
100							 processor_t			processor,
101							 thread_t			thread,
102							 integer_t			options);
103
104static void
105sched_proto_processor_queue_shutdown(
106									 processor_t			processor);
107
108static boolean_t
109sched_proto_processor_queue_remove(
110						    processor_t			processor,
111							thread_t		thread);
112
113static boolean_t
114sched_proto_processor_queue_empty(processor_t		processor);
115
116static boolean_t
117sched_proto_processor_queue_has_priority(processor_t		processor,
118										 int				priority,
119										 boolean_t		gte);
120
121static boolean_t
122sched_proto_priority_is_urgent(int priority);
123
124static ast_t
125sched_proto_processor_csw_check(processor_t processor);
126
127static uint32_t
128sched_proto_initial_quantum_size(thread_t thread);
129
130static sched_mode_t
131sched_proto_initial_thread_sched_mode(task_t parent_task);
132
133static boolean_t
134sched_proto_supports_timeshare_mode(void);
135
136static boolean_t
137sched_proto_can_update_priority(thread_t	thread);
138
139static void
140sched_proto_update_priority(thread_t	thread);
141
142static void
143sched_proto_lightweight_update_priority(thread_t	thread);
144
145static void
146sched_proto_quantum_expire(thread_t	thread);
147
148static boolean_t
149sched_proto_should_current_thread_rechoose_processor(processor_t			processor);
150
151static int
152sched_proto_processor_runq_count(processor_t   processor);
153
154static uint64_t
155sched_proto_processor_runq_stats_count_sum(processor_t   processor);
156
157const 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
193static struct run_queue	*global_runq;
194static struct run_queue	global_runq_storage;
195
196#define GLOBAL_RUNQ		((processor_t)-2)
197decl_simple_lock_data(static,global_runq_lock);
198
199extern int	max_unsafe_quanta;
200
201static uint32_t proto_quantum_us;
202static uint32_t proto_quantum;
203
204static uint32_t	runqueue_generation;
205
206static processor_t proto_processor;
207
208static uint64_t			sched_proto_tick_deadline;
209static uint32_t			sched_proto_tick;
210
211static void
212sched_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
226static void
227sched_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
246static void
247sched_proto_processor_init(processor_t processor __unused)
248{
249	/* No per-processor state */
250}
251
252static void
253sched_proto_pset_init(processor_set_t pset __unused)
254{
255}
256
257static void
258sched_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(1);
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
292static thread_t
293sched_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
353static thread_t
354sched_proto_steal_thread(processor_set_t		pset)
355{
356	pset_unlock(pset);
357
358	return (THREAD_NULL);
359
360}
361
362static void
363sched_proto_compute_priority(thread_t	thread,
364							 boolean_t			override_depress __unused)
365{
366	set_sched_pri(thread, thread->priority);
367}
368
369static processor_t
370sched_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
390static boolean_t
391sched_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
407static void
408sched_proto_processor_queue_shutdown(
409									 processor_t			processor)
410{
411	/* With a global runqueue, just stop choosing this processor */
412	(void)processor;
413}
414
415static boolean_t
416sched_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
462static boolean_t
463sched_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
472static boolean_t
473sched_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 */
492static boolean_t
493sched_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
507static ast_t
508sched_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
527static uint32_t
528sched_proto_initial_quantum_size(thread_t thread __unused)
529{
530	return proto_quantum;
531}
532
533static sched_mode_t
534sched_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
542static boolean_t
543sched_proto_supports_timeshare_mode(void)
544{
545	return TRUE;
546}
547
548static boolean_t
549sched_proto_can_update_priority(thread_t	thread __unused)
550{
551	return FALSE;
552}
553
554static void
555sched_proto_update_priority(thread_t	thread __unused)
556{
557
558}
559
560static void
561sched_proto_lightweight_update_priority(thread_t	thread __unused)
562{
563
564}
565
566static void
567sched_proto_quantum_expire(thread_t	thread __unused)
568{
569
570}
571
572static boolean_t
573sched_proto_should_current_thread_rechoose_processor(processor_t			processor)
574{
575	return (proto_processor != processor);
576}
577
578static int
579sched_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
588static uint64_t
589sched_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
598