1/*
2 * Copyright (c) 2000-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 * @OSF_COPYRIGHT@
30 */
31/*
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
49 *  School of Computer Science
50 *  Carnegie Mellon University
51 *  Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
55 */
56/*
57 */
58/*
59 *	File:	sched.h
60 *	Author:	Avadis Tevanian, Jr.
61 *	Date:	1985
62 *
63 *	Header file for scheduler.
64 *
65 */
66
67#ifndef	_KERN_SCHED_H_
68#define _KERN_SCHED_H_
69
70#include <mach/policy.h>
71#include <kern/kern_types.h>
72#include <kern/queue.h>
73#include <kern/lock.h>
74#include <kern/macro_help.h>
75#include <kern/timer_call.h>
76#include <kern/ast.h>
77
78#define	NRQS		128				/* 128 levels per run queue */
79#define NRQBM		(NRQS / 32)		/* number of words per bit map */
80
81#define MAXPRI		(NRQS-1)
82#define MINPRI		IDLEPRI			/* lowest legal priority schedulable */
83#define	IDLEPRI		0				/* idle thread priority */
84
85/*
86 *	High-level priority assignments
87 *
88 *************************************************************************
89 * 127		Reserved (real-time)
90 *				A
91 *				+
92 *			(32 levels)
93 *				+
94 *				V
95 * 96		Reserved (real-time)
96 * 95		Kernel mode only
97 *				A
98 *				+
99 *			(16 levels)
100 *				+
101 *				V
102 * 80		Kernel mode only
103 * 79		System high priority
104 *				A
105 *				+
106 *			(16 levels)
107 *				+
108 *				V
109 * 64		System high priority
110 * 63		Elevated priorities
111 *				A
112 *				+
113 *			(12 levels)
114 *				+
115 *				V
116 * 52		Elevated priorities
117 * 51		Elevated priorities (incl. BSD +nice)
118 *				A
119 *				+
120 *			(20 levels)
121 *				+
122 *				V
123 * 32		Elevated priorities (incl. BSD +nice)
124 * 31		Default (default base for threads)
125 * 30		Lowered priorities (incl. BSD -nice)
126 *				A
127 *				+
128 *			(20 levels)
129 *				+
130 *				V
131 * 11		Lowered priorities (incl. BSD -nice)
132 * 10		Lowered priorities (aged pri's)
133 *				A
134 *				+
135 *			(11 levels)
136 *				+
137 *				V
138 * 0		Lowered priorities (aged pri's / idle)
139 *************************************************************************
140 */
141
142#define BASEPRI_RTQUEUES	(BASEPRI_REALTIME + 1)				/* 97 */
143#define BASEPRI_REALTIME	(MAXPRI - (NRQS / 4) + 1)			/* 96 */
144
145#define MAXPRI_KERNEL		(BASEPRI_REALTIME - 1)				/* 95 */
146#define BASEPRI_PREEMPT		(MAXPRI_KERNEL - 2)					/* 93 */
147#define BASEPRI_KERNEL		(MINPRI_KERNEL + 1)					/* 81 */
148#define MINPRI_KERNEL		(MAXPRI_KERNEL - (NRQS / 8) + 1)	/* 80 */
149
150#define MAXPRI_RESERVED		(MINPRI_KERNEL - 1)					/* 79 */
151#define MINPRI_RESERVED		(MAXPRI_RESERVED - (NRQS / 8) + 1)	/* 64 */
152
153#define MAXPRI_USER			(MINPRI_RESERVED - 1)				/* 63 */
154#define BASEPRI_CONTROL		(BASEPRI_DEFAULT + 17)				/* 48 */
155#define BASEPRI_FOREGROUND	(BASEPRI_DEFAULT + 16)				/* 47 */
156#define BASEPRI_BACKGROUND	(BASEPRI_DEFAULT + 15)				/* 46 */
157#define BASEPRI_DEFAULT		(MAXPRI_USER - (NRQS / 4))			/* 31 */
158#define MAXPRI_THROTTLE		(MINPRI + 4)						/*  4 */
159#define MINPRI_USER			MINPRI								/*  0 */
160
161#ifdef CONFIG_EMBEDDED
162#define DEPRESSPRI	MAXPRI_THROTTLE
163#else
164#define DEPRESSPRI	MINPRI			/* depress priority */
165#endif
166
167/* Type used for thread->sched_mode and saved_mode */
168typedef enum {
169	TH_MODE_NONE = 0,					/* unassigned, usually for saved_mode only */
170	TH_MODE_REALTIME,					/* time constraints supplied */
171	TH_MODE_FIXED,						/* use fixed priorities, no decay */
172	TH_MODE_TIMESHARE,					/* use timesharing algorithm */
173	TH_MODE_FAIRSHARE					/* use fair-share scheduling */
174} sched_mode_t;
175
176/*
177 *	Macro to check for invalid priorities.
178 */
179#define invalid_pri(pri) ((pri) < MINPRI || (pri) > MAXPRI)
180
181struct runq_stats {
182	uint64_t				count_sum;
183	uint64_t				last_change_timestamp;
184};
185
186#if defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_FIXEDPRIORITY)
187
188struct run_queue {
189	int					highq;				/* highest runnable queue */
190	int					bitmap[NRQBM];		/* run queue bitmap array */
191	int					count;				/* # of threads total */
192	int					urgency;			/* level of preemption urgency */
193	queue_head_t		queues[NRQS];		/* one for each priority */
194
195	struct runq_stats	runq_stats;
196};
197
198#endif /* defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_FIXEDPRIORITY) */
199
200struct rt_queue {
201	int					count;				/* # of threads total */
202	queue_head_t		queue;				/* all runnable RT threads */
203
204	struct runq_stats	runq_stats;
205};
206
207#if defined(CONFIG_SCHED_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_FIXEDPRIORITY)
208struct fairshare_queue {
209	int					count;				/* # of threads total */
210	queue_head_t		queue;				/* all runnable threads demoted to fairshare scheduling */
211
212	struct runq_stats	runq_stats;
213};
214#endif
215
216#if defined(CONFIG_SCHED_GRRR_CORE)
217
218/*
219 * We map standard Mach priorities to an abstract scale that more properly
220 * indicates how we want processor time allocated under contention.
221 */
222typedef uint8_t	grrr_proportional_priority_t;
223typedef uint8_t grrr_group_index_t;
224
225#define NUM_GRRR_PROPORTIONAL_PRIORITIES	256
226#define MAX_GRRR_PROPORTIONAL_PRIORITY ((grrr_proportional_priority_t)255)
227
228#if 0
229#define NUM_GRRR_GROUPS 8					/* log(256) */
230#endif
231
232#define NUM_GRRR_GROUPS 64					/* 256/4 */
233
234struct grrr_group {
235	queue_chain_t			priority_order;				/* next greatest weight group */
236	grrr_proportional_priority_t		minpriority;
237	grrr_group_index_t		index;
238
239	queue_head_t			clients;
240	int						count;
241	uint32_t				weight;
242#if 0
243	uint32_t				deferred_removal_weight;
244#endif
245	uint32_t				work;
246	thread_t				current_client;
247};
248
249struct grrr_run_queue {
250	int					count;
251	uint32_t			last_rescale_tick;
252	struct grrr_group	groups[NUM_GRRR_GROUPS];
253	queue_head_t		sorted_group_list;
254	uint32_t			weight;
255	grrr_group_t		current_group;
256
257	struct runq_stats   runq_stats;
258};
259
260#endif /* defined(CONFIG_SCHED_GRRR_CORE) */
261
262#define first_timeslice(processor)		((processor)->timeslice > 0)
263
264extern struct rt_queue		rt_runq;
265
266/*
267 *	Scheduler routines.
268 */
269
270/* Handle quantum expiration for an executing thread */
271extern void		thread_quantum_expire(
272					timer_call_param_t	processor,
273					timer_call_param_t	thread);
274
275/* Context switch check for current processor */
276extern ast_t	csw_check(processor_t		processor);
277
278#if defined(CONFIG_SCHED_TRADITIONAL)
279extern uint32_t	std_quantum, min_std_quantum;
280extern uint32_t	std_quantum_us;
281#endif
282
283extern uint32_t thread_depress_time;
284extern uint32_t default_timeshare_computation;
285extern uint32_t default_timeshare_constraint;
286
287extern uint32_t	max_rt_quantum, min_rt_quantum;
288
289extern int default_preemption_rate;
290extern int default_bg_preemption_rate;
291
292#if defined(CONFIG_SCHED_TRADITIONAL)
293
294/*
295 *	Age usage (1 << SCHED_TICK_SHIFT) times per second.
296 */
297#define SCHED_TICK_SHIFT	3
298
299extern unsigned		sched_tick;
300extern uint32_t		sched_tick_interval;
301
302#endif /* CONFIG_SCHED_TRADITIONAL */
303
304extern uint64_t		sched_one_second_interval;
305
306/* Periodic computation of various averages */
307extern void		compute_averages(void);
308
309extern void		compute_averunnable(
310					void			*nrun);
311
312extern void		compute_stack_target(
313					void			*arg);
314
315extern void		compute_memory_pressure(
316					void			*arg);
317
318extern void		compute_zone_gc_throttle(
319					void			*arg);
320
321extern void		compute_pageout_gc_throttle(
322					void			*arg);
323
324extern void		compute_pmap_gc_throttle(
325					void			*arg);
326
327/*
328 *	Conversion factor from usage
329 *	to priority.
330 */
331#if defined(CONFIG_SCHED_TRADITIONAL)
332extern uint32_t		sched_pri_shift;
333extern uint32_t		sched_fixed_shift;
334extern int8_t		sched_load_shifts[NRQS];
335#endif
336
337extern int32_t		sched_poll_yield_shift;
338extern uint64_t		sched_safe_duration;
339
340extern uint32_t		sched_run_count, sched_share_count;
341extern uint32_t		sched_load_average, sched_mach_factor;
342
343extern uint32_t		avenrun[3], mach_factor[3];
344
345extern uint64_t		max_unsafe_computation;
346extern uint64_t		max_poll_computation;
347
348#define sched_run_incr()			\
349MACRO_BEGIN					\
350         hw_atomic_add(&sched_run_count, 1);	\
351MACRO_END
352
353#define sched_run_decr()			\
354MACRO_BEGIN					\
355	hw_atomic_sub(&sched_run_count, 1);	\
356MACRO_END
357
358#define sched_share_incr()			\
359MACRO_BEGIN											\
360	(void)hw_atomic_add(&sched_share_count, 1);		\
361MACRO_END
362
363#define sched_share_decr()			\
364MACRO_BEGIN											\
365	(void)hw_atomic_sub(&sched_share_count, 1);		\
366MACRO_END
367
368/*
369 *	thread_timer_delta macro takes care of both thread timers.
370 */
371#define thread_timer_delta(thread, delta)					\
372MACRO_BEGIN													\
373	(delta) = (typeof(delta))timer_delta(&(thread)->system_timer,			\
374							&(thread)->system_timer_save);	\
375	(delta) += (typeof(delta))timer_delta(&(thread)->user_timer,			\
376							&(thread)->user_timer_save);	\
377MACRO_END
378
379#endif	/* _KERN_SCHED_H_ */
380