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/smp.h>
73#include <kern/queue.h>
74#include <kern/macro_help.h>
75#include <kern/timer_call.h>
76#include <kern/ast.h>
77#include <kern/kalloc.h>
78#include <kern/bits.h>
79
80#define NRQS 128 /* 128 levels per run queue */
81
82#define MAXPRI (NRQS-1)
83#define MINPRI 0 /* lowest legal priority schedulable */
84#define IDLEPRI MINPRI /* idle thread priority */
85#define NOPRI -1
86
87/*
88 * High-level priority assignments
89 *
90 *************************************************************************
91 * 127 Reserved (real-time)
92 * A
93 * +
94 * (32 levels)
95 * +
96 * V
97 * 96 Reserved (real-time)
98 * 95 Kernel mode only
99 * A
100 * +
101 * (16 levels)
102 * +
103 * V
104 * 80 Kernel mode only
105 * 79 System high priority
106 * A
107 * +
108 * (16 levels)
109 * +
110 * V
111 * 64 System high priority
112 * 63 Elevated priorities
113 * A
114 * +
115 * (12 levels)
116 * +
117 * V
118 * 52 Elevated priorities
119 * 51 Elevated priorities (incl. BSD +nice)
120 * A
121 * +
122 * (20 levels)
123 * +
124 * V
125 * 32 Elevated priorities (incl. BSD +nice)
126 * 31 Default (default base for threads)
127 * 30 Lowered priorities (incl. BSD -nice)
128 * A
129 * +
130 * (20 levels)
131 * +
132 * V
133 * 11 Lowered priorities (incl. BSD -nice)
134 * 10 Lowered priorities (aged pri's)
135 * A
136 * +
137 * (11 levels)
138 * +
139 * V
140 * 0 Lowered priorities (aged pri's / idle)
141 *************************************************************************
142 */
143
144#define BASEPRI_RTQUEUES (BASEPRI_REALTIME + 1) /* 97 */
145#define BASEPRI_REALTIME (MAXPRI - (NRQS / 4) + 1) /* 96 */
146
147#define MAXPRI_KERNEL (BASEPRI_REALTIME - 1) /* 95 */
148#define BASEPRI_PREEMPT_HIGH (BASEPRI_PREEMPT + 1) /* 93 */
149#define BASEPRI_PREEMPT (MAXPRI_KERNEL - 3) /* 92 */
150#define BASEPRI_VM (BASEPRI_PREEMPT - 1) /* 91 */
151
152#define BASEPRI_KERNEL (MINPRI_KERNEL + 1) /* 81 */
153#define MINPRI_KERNEL (MAXPRI_KERNEL - (NRQS / 8) + 1) /* 80 */
154
155#define MAXPRI_RESERVED (MINPRI_KERNEL - 1) /* 79 */
156#define BASEPRI_GRAPHICS (MAXPRI_RESERVED - 3) /* 76 */
157#define MINPRI_RESERVED (MAXPRI_RESERVED - (NRQS / 8) + 1) /* 64 */
158
159#define MAXPRI_USER (MINPRI_RESERVED - 1) /* 63 */
160#define BASEPRI_CONTROL (BASEPRI_DEFAULT + 17) /* 48 */
161#define BASEPRI_FOREGROUND (BASEPRI_DEFAULT + 16) /* 47 */
162#define BASEPRI_BACKGROUND (BASEPRI_DEFAULT + 15) /* 46 */
163#define BASEPRI_USER_INITIATED (BASEPRI_DEFAULT + 6) /* 37 */
164#define BASEPRI_DEFAULT (MAXPRI_USER - (NRQS / 4)) /* 31 */
165#define MAXPRI_SUPPRESSED (BASEPRI_DEFAULT - 3) /* 28 */
166#define BASEPRI_UTILITY (BASEPRI_DEFAULT - 11) /* 20 */
167#define MAXPRI_THROTTLE (MINPRI + 4) /* 4 */
168#define MINPRI_USER MINPRI /* 0 */
169
170#define DEPRESSPRI (MINPRI) /* depress priority */
171
172#define MAXPRI_PROMOTE (MAXPRI_KERNEL) /* ceiling for mutex promotion */
173#define MINPRI_RWLOCK (BASEPRI_BACKGROUND) /* floor when holding rwlock count */
174#define MINPRI_EXEC (BASEPRI_DEFAULT) /* floor when in exec state */
175#define MINPRI_WAITQ (BASEPRI_DEFAULT) /* floor when in waitq handover state */
176
177
178/* Type used for thread->sched_mode and saved_mode */
179typedef enum {
180 TH_MODE_NONE = 0, /* unassigned, usually for saved_mode only */
181 TH_MODE_REALTIME, /* time constraints supplied */
182 TH_MODE_FIXED, /* use fixed priorities, no decay */
183 TH_MODE_TIMESHARE, /* use timesharing algorithm */
184} sched_mode_t;
185
186/* Buckets used for load calculation */
187typedef enum {
188 TH_BUCKET_RUN = 0, /* All runnable threads */
189 TH_BUCKET_FIXPRI, /* Fixed-priority */
190 TH_BUCKET_SHARE_FG, /* Timeshare thread above BASEPRI_DEFAULT */
191 TH_BUCKET_SHARE_DF, /* Timeshare thread between BASEPRI_DEFAULT and BASEPRI_UTILITY */
192 TH_BUCKET_SHARE_UT, /* Timeshare thread between BASEPRI_UTILITY and MAXPRI_THROTTLE */
193 TH_BUCKET_SHARE_BG, /* Timeshare thread between MAXPRI_THROTTLE and MINPRI */
194 TH_BUCKET_MAX,
195} sched_bucket_t;
196
197/*
198 * Macro to check for invalid priorities.
199 */
200#define invalid_pri(pri) ((pri) < MINPRI || (pri) > MAXPRI)
201
202struct runq_stats {
203 uint64_t count_sum;
204 uint64_t last_change_timestamp;
205};
206
207#if defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO)
208
209struct run_queue {
210 int highq; /* highest runnable queue */
211 bitmap_t bitmap[BITMAP_LEN(NRQS)]; /* run queue bitmap array */
212 int count; /* # of threads total */
213 int urgency; /* level of preemption urgency */
214 queue_head_t queues[NRQS]; /* one for each priority */
215
216 struct runq_stats runq_stats;
217};
218
219inline static void
220rq_bitmap_set(bitmap_t *map, u_int n)
221{
222 assert(n < NRQS);
223 bitmap_set(map, n);
224}
225
226inline static void
227rq_bitmap_clear(bitmap_t *map, u_int n)
228{
229 assert(n < NRQS);
230 bitmap_clear(map, n);
231}
232
233#endif /* defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO) */
234
235struct rt_queue {
236 _Atomic int count; /* # of threads total */
237 queue_head_t queue; /* all runnable RT threads */
238#if __SMP__
239 decl_simple_lock_data(,rt_lock)
240#endif
241 struct runq_stats runq_stats;
242};
243typedef struct rt_queue *rt_queue_t;
244
245#if defined(CONFIG_SCHED_GRRR_CORE)
246
247/*
248 * We map standard Mach priorities to an abstract scale that more properly
249 * indicates how we want processor time allocated under contention.
250 */
251typedef uint8_t grrr_proportional_priority_t;
252typedef uint8_t grrr_group_index_t;
253
254#define NUM_GRRR_PROPORTIONAL_PRIORITIES 256
255#define MAX_GRRR_PROPORTIONAL_PRIORITY ((grrr_proportional_priority_t)255)
256
257#if 0
258#define NUM_GRRR_GROUPS 8 /* log(256) */
259#endif
260
261#define NUM_GRRR_GROUPS 64 /* 256/4 */
262
263struct grrr_group {
264 queue_chain_t priority_order; /* next greatest weight group */
265 grrr_proportional_priority_t minpriority;
266 grrr_group_index_t index;
267
268 queue_head_t clients;
269 int count;
270 uint32_t weight;
271#if 0
272 uint32_t deferred_removal_weight;
273#endif
274 uint32_t work;
275 thread_t current_client;
276};
277
278struct grrr_run_queue {
279 int count;
280 uint32_t last_rescale_tick;
281 struct grrr_group groups[NUM_GRRR_GROUPS];
282 queue_head_t sorted_group_list;
283 uint32_t weight;
284 grrr_group_t current_group;
285
286 struct runq_stats runq_stats;
287};
288
289#endif /* defined(CONFIG_SCHED_GRRR_CORE) */
290
291extern int rt_runq_count(processor_set_t);
292extern void rt_runq_count_incr(processor_set_t);
293extern void rt_runq_count_decr(processor_set_t);
294
295#if defined(CONFIG_SCHED_MULTIQ)
296sched_group_t sched_group_create(void);
297void sched_group_destroy(sched_group_t sched_group);
298#endif /* defined(CONFIG_SCHED_MULTIQ) */
299
300
301
302/*
303 * Scheduler routines.
304 */
305
306/* Handle quantum expiration for an executing thread */
307extern void thread_quantum_expire(
308 timer_call_param_t processor,
309 timer_call_param_t thread);
310
311/* Context switch check for current processor */
312extern ast_t csw_check(processor_t processor,
313 ast_t check_reason);
314
315extern void sched_update_generation_count(void);
316
317#if defined(CONFIG_SCHED_TIMESHARE_CORE)
318extern uint32_t std_quantum, min_std_quantum;
319extern uint32_t std_quantum_us;
320#endif /* CONFIG_SCHED_TIMESHARE_CORE */
321
322extern uint32_t thread_depress_time;
323extern uint32_t default_timeshare_computation;
324extern uint32_t default_timeshare_constraint;
325
326extern uint32_t max_rt_quantum, min_rt_quantum;
327
328extern int default_preemption_rate;
329extern int default_bg_preemption_rate;
330
331#if defined(CONFIG_SCHED_TIMESHARE_CORE)
332
333/*
334 * Age usage at approximately (1 << SCHED_TICK_SHIFT) times per second
335 * Aging may be deferred during periods where all processors are idle
336 * and cumulatively applied during periods of activity.
337 */
338#define SCHED_TICK_SHIFT 3
339#define SCHED_TICK_MAX_DELTA (8)
340
341extern unsigned sched_tick;
342extern uint32_t sched_tick_interval;
343
344#endif /* CONFIG_SCHED_TIMESHARE_CORE */
345
346extern uint64_t sched_one_second_interval;
347
348/* Periodic computation of various averages */
349extern void compute_sched_load(void);
350
351extern void compute_averages(uint64_t);
352
353extern void compute_averunnable(
354 void *nrun);
355
356extern void compute_stack_target(
357 void *arg);
358
359extern void compute_pageout_gc_throttle(
360 void *arg);
361
362extern void compute_pmap_gc_throttle(
363 void *arg);
364
365/*
366 * Conversion factor from usage
367 * to priority.
368 */
369#if defined(CONFIG_SCHED_TIMESHARE_CORE)
370
371#define MAX_LOAD (NRQS - 1)
372extern uint32_t sched_pri_shifts[TH_BUCKET_MAX];
373extern uint32_t sched_fixed_shift;
374extern int8_t sched_load_shifts[NRQS];
375extern uint32_t sched_decay_usage_age_factor;
376void sched_timeshare_consider_maintenance(uint64_t ctime);
377#endif /* CONFIG_SCHED_TIMESHARE_CORE */
378
379void sched_consider_recommended_cores(uint64_t ctime, thread_t thread);
380
381extern int32_t sched_poll_yield_shift;
382extern uint64_t sched_safe_duration;
383
384extern uint32_t sched_load_average, sched_mach_factor;
385
386extern uint32_t avenrun[3], mach_factor[3];
387
388extern uint64_t max_unsafe_computation;
389extern uint64_t max_poll_computation;
390
391extern volatile uint32_t sched_run_buckets[TH_BUCKET_MAX];
392
393extern uint32_t sched_run_incr(thread_t thread);
394extern uint32_t sched_run_decr(thread_t thread);
395
396/*
397 * thread_timer_delta macro takes care of both thread timers.
398 */
399#define thread_timer_delta(thread, delta) \
400MACRO_BEGIN \
401 (delta) = (typeof(delta))timer_delta(&(thread)->system_timer, \
402 &(thread)->system_timer_save); \
403 (delta) += (typeof(delta))timer_delta(&(thread)->user_timer, \
404 &(thread)->user_timer_save); \
405MACRO_END
406
407#endif /* _KERN_SCHED_H_ */
408