1/*
2 * Copyright (c) 2000-2008 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 <stat_time.h>
71
72#include <mach/policy.h>
73#include <kern/kern_types.h>
74#include <kern/queue.h>
75#include <kern/lock.h>
76#include <kern/macro_help.h>
77#include <kern/timer_call.h>
78#include <kern/ast.h>
79
80#define	NRQS		128				/* 128 levels per run queue */
81#define NRQBM		(NRQS / 32)		/* number of words per bit map */
82
83#define MAXPRI		(NRQS-1)
84#define MINPRI		IDLEPRI			/* lowest legal priority schedulable */
85#define	IDLEPRI		0				/* idle thread priority */
86#define DEPRESSPRI	MINPRI			/* depress priority */
87
88/*
89 *	High-level priority assignments
90 *
91 *************************************************************************
92 * 127		Reserved (real-time)
93 *				A
94 *				+
95 *			(32 levels)
96 *				+
97 *				V
98 * 96		Reserved (real-time)
99 * 95		Kernel mode only
100 *				A
101 *				+
102 *			(16 levels)
103 *				+
104 *				V
105 * 80		Kernel mode only
106 * 79		System high priority
107 *				A
108 *				+
109 *			(16 levels)
110 *				+
111 *				V
112 * 64		System high priority
113 * 63		Elevated priorities
114 *				A
115 *				+
116 *			(12 levels)
117 *				+
118 *				V
119 * 52		Elevated priorities
120 * 51		Elevated priorities (incl. BSD +nice)
121 *				A
122 *				+
123 *			(20 levels)
124 *				+
125 *				V
126 * 32		Elevated priorities (incl. BSD +nice)
127 * 31		Default (default base for threads)
128 * 30		Lowered priorities (incl. BSD -nice)
129 *				A
130 *				+
131 *			(20 levels)
132 *				+
133 *				V
134 * 11		Lowered priorities (incl. BSD -nice)
135 * 10		Lowered priorities (aged pri's)
136 *				A
137 *				+
138 *			(11 levels)
139 *				+
140 *				V
141 * 0		Lowered priorities (aged pri's / idle)
142 *************************************************************************
143 */
144
145#define BASEPRI_RTQUEUES	(BASEPRI_REALTIME + 1)				/* 97 */
146#define BASEPRI_REALTIME	(MAXPRI - (NRQS / 4) + 1)			/* 96 */
147
148#define MAXPRI_KERNEL		(BASEPRI_REALTIME - 1)				/* 95 */
149#define BASEPRI_PREEMPT		(MAXPRI_KERNEL - 2)					/* 93 */
150#define BASEPRI_KERNEL		(MINPRI_KERNEL + 1)					/* 81 */
151#define MINPRI_KERNEL		(MAXPRI_KERNEL - (NRQS / 8) + 1)	/* 80 */
152
153#define MAXPRI_RESERVED		(MINPRI_KERNEL - 1)					/* 79 */
154#define MINPRI_RESERVED		(MAXPRI_RESERVED - (NRQS / 8) + 1)	/* 64 */
155
156#define MAXPRI_USER			(MINPRI_RESERVED - 1)				/* 63 */
157#define BASEPRI_CONTROL		(BASEPRI_DEFAULT + 17)				/* 48 */
158#define BASEPRI_FOREGROUND	(BASEPRI_DEFAULT + 16)				/* 47 */
159#define BASEPRI_BACKGROUND	(BASEPRI_DEFAULT + 15)				/* 46 */
160#define BASEPRI_DEFAULT		(MAXPRI_USER - (NRQS / 4))			/* 31 */
161#define MINPRI_USER			MINPRI								/*  0 */
162
163/*
164 *	Macro to check for invalid priorities.
165 */
166#define invalid_pri(pri) ((pri) < MINPRI || (pri) > MAXPRI)
167
168struct run_queue {
169	int					highq;				/* highest runnable queue */
170	int					bitmap[NRQBM];		/* run queue bitmap array */
171	int					count;				/* # of threads total */
172	int					urgency;			/* level of preemption urgency */
173	queue_head_t		queues[NRQS];		/* one for each priority */
174};
175
176typedef struct run_queue	*run_queue_t;
177#define RUN_QUEUE_NULL		((run_queue_t) 0)
178
179#define first_timeslice(processor)		((processor)->timeslice > 0)
180
181#define thread_quantum_init(thread)							\
182MACRO_BEGIN													\
183	(thread)->current_quantum = 							\
184		((thread)->sched_mode & TH_MODE_REALTIME)?			\
185			(thread)->realtime.computation: std_quantum;	\
186MACRO_END
187
188extern struct run_queue		rt_runq;
189
190/*
191 *	Scheduler routines.
192 */
193
194/* Remove thread from its run queue */
195extern boolean_t	run_queue_remove(
196						thread_t	thread);
197
198/* Handle quantum expiration for an executing thread */
199extern void		thread_quantum_expire(
200					timer_call_param_t	processor,
201					timer_call_param_t	thread);
202
203/* Context switch check for current processor */
204extern ast_t	csw_check(processor_t		processor);
205
206extern uint32_t	std_quantum, min_std_quantum;
207extern uint32_t	std_quantum_us;
208
209extern uint32_t	max_rt_quantum, min_rt_quantum;
210
211extern uint32_t	sched_cswtime;
212
213/*
214 *	Age usage (1 << SCHED_TICK_SHIFT) times per second.
215 */
216#define SCHED_TICK_SHIFT	3
217
218extern unsigned		sched_tick;
219extern uint32_t		sched_tick_interval;
220
221/* Periodic computation of various averages */
222extern void		compute_averages(void);
223
224extern void		compute_averunnable(
225					void			*nrun);
226
227extern void		compute_stack_target(
228					void			*arg);
229
230/*
231 *	Conversion factor from usage
232 *	to priority.
233 */
234extern uint32_t		sched_pri_shift;
235extern uint32_t		sched_fixed_shift;
236extern int8_t		sched_load_shifts[NRQS];
237
238extern int32_t		sched_poll_yield_shift;
239extern uint32_t		sched_safe_duration;
240
241extern uint32_t		sched_run_count, sched_share_count;
242extern uint32_t		sched_load_average, sched_mach_factor;
243
244extern uint32_t		avenrun[3], mach_factor[3];
245
246extern uint64_t		max_unsafe_computation;
247extern uint64_t		max_poll_computation;
248
249#define sched_run_incr()			\
250MACRO_BEGIN													\
251	machine_run_count(hw_atomic_add(&sched_run_count, 1));	\
252MACRO_END
253
254#define sched_run_decr()			\
255MACRO_BEGIN													\
256	machine_run_count(hw_atomic_sub(&sched_run_count, 1));	\
257MACRO_END
258
259#define sched_share_incr()			\
260MACRO_BEGIN											\
261	(void)hw_atomic_add(&sched_share_count, 1);		\
262MACRO_END
263
264#define sched_share_decr()			\
265MACRO_BEGIN											\
266	(void)hw_atomic_sub(&sched_share_count, 1);		\
267MACRO_END
268
269/*
270 *	thread_timer_delta macro takes care of both thread timers.
271 */
272#define thread_timer_delta(thread, delta)					\
273MACRO_BEGIN													\
274	(delta) = timer_delta(&(thread)->system_timer,			\
275							&(thread)->system_timer_save);	\
276	(delta) += timer_delta(&(thread)->user_timer,			\
277							&(thread)->user_timer_save);	\
278MACRO_END
279
280#endif	/* _KERN_SCHED_H_ */
281