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/macro_help.h>
74#include <kern/timer_call.h>
75#include <kern/ast.h>
76
77#define	NRQS		128				/* 128 levels per run queue */
78#define NRQBM		(NRQS / 32)		/* number of words per bit map */
79
80#define MAXPRI		(NRQS-1)
81#define MINPRI		IDLEPRI			/* lowest legal priority schedulable */
82#define	IDLEPRI		0				/* idle thread priority */
83
84/*
85 *	High-level priority assignments
86 *
87 *************************************************************************
88 * 127		Reserved (real-time)
89 *				A
90 *				+
91 *			(32 levels)
92 *				+
93 *				V
94 * 96		Reserved (real-time)
95 * 95		Kernel mode only
96 *				A
97 *				+
98 *			(16 levels)
99 *				+
100 *				V
101 * 80		Kernel mode only
102 * 79		System high priority
103 *				A
104 *				+
105 *			(16 levels)
106 *				+
107 *				V
108 * 64		System high priority
109 * 63		Elevated priorities
110 *				A
111 *				+
112 *			(12 levels)
113 *				+
114 *				V
115 * 52		Elevated priorities
116 * 51		Elevated priorities (incl. BSD +nice)
117 *				A
118 *				+
119 *			(20 levels)
120 *				+
121 *				V
122 * 32		Elevated priorities (incl. BSD +nice)
123 * 31		Default (default base for threads)
124 * 30		Lowered priorities (incl. BSD -nice)
125 *				A
126 *				+
127 *			(20 levels)
128 *				+
129 *				V
130 * 11		Lowered priorities (incl. BSD -nice)
131 * 10		Lowered priorities (aged pri's)
132 *				A
133 *				+
134 *			(11 levels)
135 *				+
136 *				V
137 * 0		Lowered priorities (aged pri's / idle)
138 *************************************************************************
139 */
140
141#define BASEPRI_RTQUEUES	(BASEPRI_REALTIME + 1)				/* 97 */
142#define BASEPRI_REALTIME	(MAXPRI - (NRQS / 4) + 1)			/* 96 */
143
144#define MAXPRI_KERNEL		(BASEPRI_REALTIME - 1)				/* 95 */
145#define BASEPRI_PREEMPT		(MAXPRI_KERNEL - 2)					/* 93 */
146#define BASEPRI_KERNEL		(MINPRI_KERNEL + 1)					/* 81 */
147#define MINPRI_KERNEL		(MAXPRI_KERNEL - (NRQS / 8) + 1)	/* 80 */
148
149#define MAXPRI_RESERVED		(MINPRI_KERNEL - 1)					/* 79 */
150#define BASEPRI_GRAPHICS	(MAXPRI_RESERVED - 3)				/* 76 */
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_USER_INITIATED	(BASEPRI_DEFAULT +  6)				/* 37 */
158#define BASEPRI_DEFAULT		(MAXPRI_USER - (NRQS / 4))			/* 31 */
159#define MAXPRI_SUPPRESSED	(BASEPRI_DEFAULT - 3)				/* 28 */
160#define BASEPRI_UTILITY		(BASEPRI_DEFAULT - 11)				/* 20 */
161#define MAXPRI_THROTTLE		(MINPRI + 4)						/*  4 */
162#define MINPRI_USER			MINPRI								/*  0 */
163
164#define DEPRESSPRI	MINPRI			/* depress priority */
165#define MAXPRI_PROMOTE		(MAXPRI_KERNEL)		/* ceiling for mutex promotion */
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_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO)
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_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO) */
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_FAIRSHARE_CORE)
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 /* CONFIG_SCHED_FAIRSHARE_CORE */
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#if defined(CONFIG_SCHED_MULTIQ)
267sched_group_t   sched_group_create(void);
268void            sched_group_destroy(sched_group_t sched_group);
269
270extern boolean_t sched_groups_enabled;
271
272#endif /* defined(CONFIG_SCHED_MULTIQ) */
273
274/*
275 *	Scheduler routines.
276 */
277
278/* Handle quantum expiration for an executing thread */
279extern void		thread_quantum_expire(
280					timer_call_param_t	processor,
281					timer_call_param_t	thread);
282
283/* Context switch check for current processor */
284extern ast_t	csw_check(processor_t		processor,
285						ast_t			check_reason);
286
287#if defined(CONFIG_SCHED_TIMESHARE_CORE)
288extern uint32_t	std_quantum, min_std_quantum;
289extern uint32_t	std_quantum_us;
290#endif /* CONFIG_SCHED_TIMESHARE_CORE */
291
292extern uint32_t thread_depress_time;
293extern uint32_t default_timeshare_computation;
294extern uint32_t default_timeshare_constraint;
295
296extern uint32_t	max_rt_quantum, min_rt_quantum;
297
298extern int default_preemption_rate;
299extern int default_bg_preemption_rate;
300
301#if defined(CONFIG_SCHED_TIMESHARE_CORE)
302
303/*
304 *	Age usage  at approximately (1 << SCHED_TICK_SHIFT) times per second
305 *	Aging may be deferred during periods where all processors are idle
306 *	and cumulatively applied during periods of activity.
307 */
308#define SCHED_TICK_SHIFT	3
309#define SCHED_TICK_MAX_DELTA	(8)
310
311extern unsigned		sched_tick;
312extern uint32_t		sched_tick_interval;
313
314#endif /* CONFIG_SCHED_TIMESHARE_CORE */
315
316extern uint64_t		sched_one_second_interval;
317
318/* Periodic computation of various averages */
319extern void		compute_averages(uint64_t);
320
321extern void		compute_averunnable(
322					void			*nrun);
323
324extern void		compute_stack_target(
325					void			*arg);
326
327extern void		compute_memory_pressure(
328					void			*arg);
329
330extern void		compute_zone_gc_throttle(
331					void			*arg);
332
333extern void		compute_pageout_gc_throttle(
334					void			*arg);
335
336extern void		compute_pmap_gc_throttle(
337					void			*arg);
338
339/*
340 *	Conversion factor from usage
341 *	to priority.
342 */
343#if defined(CONFIG_SCHED_TIMESHARE_CORE)
344extern uint32_t		sched_pri_shift;
345extern uint32_t		sched_background_pri_shift;
346extern uint32_t		sched_combined_fgbg_pri_shift;
347extern uint32_t		sched_fixed_shift;
348extern int8_t		sched_load_shifts[NRQS];
349extern uint32_t		sched_decay_usage_age_factor;
350extern uint32_t		sched_use_combined_fgbg_decay;
351void sched_traditional_consider_maintenance(uint64_t);
352#endif /* CONFIG_SCHED_TIMESHARE_CORE */
353
354extern int32_t		sched_poll_yield_shift;
355extern uint64_t		sched_safe_duration;
356
357extern uint32_t		sched_run_count, sched_share_count, sched_background_count;
358extern uint32_t		sched_load_average, sched_mach_factor;
359
360extern uint32_t		avenrun[3], mach_factor[3];
361
362extern uint64_t		max_unsafe_computation;
363extern uint64_t		max_poll_computation;
364
365/* TH_RUN & !TH_IDLE controls whether a thread has a run count */
366#define sched_run_incr(th)                                      \
367	hw_atomic_add(&sched_run_count, 1)                      \
368
369#define sched_run_decr(th)                                      \
370	hw_atomic_sub(&sched_run_count, 1)                      \
371
372#if MACH_ASSERT
373extern void sched_share_incr(thread_t thread);
374extern void sched_share_decr(thread_t thread);
375extern void sched_background_incr(thread_t thread);
376extern void sched_background_decr(thread_t thread);
377
378extern void assert_thread_sched_count(thread_t thread);
379
380#else /* MACH_ASSERT */
381/* sched_mode == TH_MODE_TIMESHARE controls whether a thread has a timeshare count when it has a run count */
382#define sched_share_incr(th)                            \
383MACRO_BEGIN                                             \
384	(void)hw_atomic_add(&sched_share_count, 1);     \
385MACRO_END
386
387#define sched_share_decr(th)                            \
388MACRO_BEGIN                                             \
389	(void)hw_atomic_sub(&sched_share_count, 1);     \
390MACRO_END
391
392/* TH_SFLAG_THROTTLED controls whether a thread has a background count when it has a run count and a share count */
393#define sched_background_incr(th)                       \
394MACRO_BEGIN                                             \
395	hw_atomic_add(&sched_background_count, 1);      \
396MACRO_END
397
398#define sched_background_decr(th)                       \
399MACRO_BEGIN                                             \
400	hw_atomic_sub(&sched_background_count, 1);      \
401MACRO_END
402
403#define assert_thread_sched_count(th)                   \
404MACRO_BEGIN                                             \
405MACRO_END
406
407#endif /* !MACH_ASSERT */
408
409/*
410 *	thread_timer_delta macro takes care of both thread timers.
411 */
412#define thread_timer_delta(thread, delta)					\
413MACRO_BEGIN													\
414	(delta) = (typeof(delta))timer_delta(&(thread)->system_timer,			\
415							&(thread)->system_timer_save);	\
416	(delta) += (typeof(delta))timer_delta(&(thread)->user_timer,			\
417							&(thread)->user_timer_save);	\
418MACRO_END
419
420#endif	/* _KERN_SCHED_H_ */
421