1 /*
2 * Copyright (c) 2000-2016 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_FREE_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 [email protected]
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_prim.c
60 * Author: Avadis Tevanian, Jr.
61 * Date: 1986
62 *
63 * Scheduling primitives
64 *
65 */
66
67 /*
68 * This version of osfmk/kern/sched_prim.c contains the limited subset of dependencies strictly
69 * required by the Clutch runqueue test harness in tests/sched/sched_test_harness/sched_clutch_harness.c.
70 * The dependencies have been copied here in order to isolate maintenance of the Clutch test
71 * harness from the rest of xnu.
72 */
73 #if !SCHED_TEST_HARNESS
74 #error File only for use with the Clutch runqueue test harness
75 #endif
76
77 #include <kern/sched_prim.h>
78
79 boolean_t
priority_is_urgent(int priority)80 priority_is_urgent(int priority)
81 {
82 if (priority <= BASEPRI_FOREGROUND) {
83 return FALSE;
84 }
85 if (priority < MINPRI_KERNEL) {
86 return TRUE;
87 }
88 if (priority >= BASEPRI_PREEMPT) {
89 return TRUE;
90 }
91 return FALSE;
92 }
93
94 /*
95 * run_queue_init:
96 *
97 * Initialize a run queue before first use.
98 */
99 void
run_queue_init(run_queue_t rq)100 run_queue_init(
101 run_queue_t rq)
102 {
103 rq->highq = NOPRI;
104 for (u_int i = 0; i < BITMAP_LEN(NRQS); i++) {
105 rq->bitmap[i] = 0;
106 }
107 rq->urgency = rq->count = 0;
108 for (int i = 0; i < NRQS; i++) {
109 circle_queue_init(&rq->queues[i]);
110 }
111 }
112 /*
113 * run_queue_dequeue:
114 *
115 * Perform a dequeue operation on a run queue,
116 * and return the resulting thread.
117 *
118 * The run queue must be locked (see thread_run_queue_remove()
119 * for more info), and not empty.
120 */
121 thread_t
run_queue_dequeue(run_queue_t rq,sched_options_t options)122 run_queue_dequeue(
123 run_queue_t rq,
124 sched_options_t options)
125 {
126 thread_t thread;
127 circle_queue_t queue = &rq->queues[rq->highq];
128
129 if (options & SCHED_HEADQ) {
130 thread = cqe_dequeue_head(queue, struct thread, runq_links);
131 } else {
132 thread = cqe_dequeue_tail(queue, struct thread, runq_links);
133 }
134
135 assert(thread != THREAD_NULL);
136
137 thread_clear_runq(thread);
138 rq->count--;
139 if (SCHED(priority_is_urgent)(rq->highq)) {
140 rq->urgency--; assert(rq->urgency >= 0);
141 }
142 if (circle_queue_empty(queue)) {
143 bitmap_clear(rq->bitmap, rq->highq);
144 rq->highq = bitmap_first(rq->bitmap, NRQS);
145 }
146
147 return thread;
148 }
149
150 /*
151 * run_queue_enqueue:
152 *
153 * Perform a enqueue operation on a run queue.
154 *
155 * The run queue must be locked (see thread_run_queue_remove()
156 * for more info).
157 */
158 boolean_t
run_queue_enqueue(run_queue_t rq,thread_t thread,sched_options_t options)159 run_queue_enqueue(
160 run_queue_t rq,
161 thread_t thread,
162 sched_options_t options)
163 {
164 circle_queue_t queue = &rq->queues[thread->sched_pri];
165 boolean_t result = FALSE;
166
167 if (circle_queue_empty(queue)) {
168 circle_enqueue_tail(queue, &thread->runq_links);
169
170 rq_bitmap_set(rq->bitmap, thread->sched_pri);
171 if (thread->sched_pri > rq->highq) {
172 rq->highq = thread->sched_pri;
173 result = TRUE;
174 }
175 } else {
176 if (options & SCHED_TAILQ) {
177 circle_enqueue_tail(queue, &thread->runq_links);
178 } else {
179 circle_enqueue_head(queue, &thread->runq_links);
180 }
181 }
182 if (SCHED(priority_is_urgent)(thread->sched_pri)) {
183 rq->urgency++;
184 }
185 rq->count++;
186
187 return result;
188 }
189
190 /*
191 * run_queue_remove:
192 *
193 * Remove a specific thread from a runqueue.
194 *
195 * The run queue must be locked.
196 */
197 void
run_queue_remove(run_queue_t rq,thread_t thread)198 run_queue_remove(
199 run_queue_t rq,
200 thread_t thread)
201 {
202 circle_queue_t queue = &rq->queues[thread->sched_pri];
203
204 thread_assert_runq_nonnull(thread);
205
206 circle_dequeue(queue, &thread->runq_links);
207 rq->count--;
208 if (SCHED(priority_is_urgent)(thread->sched_pri)) {
209 rq->urgency--; assert(rq->urgency >= 0);
210 }
211
212 if (circle_queue_empty(queue)) {
213 /* update run queue status */
214 bitmap_clear(rq->bitmap, thread->sched_pri);
215 rq->highq = bitmap_first(rq->bitmap, NRQS);
216 }
217
218 thread_clear_runq(thread);
219 }
220
221 /*
222 * run_queue_peek
223 *
224 * Peek at the runq and return the highest
225 * priority thread from the runq.
226 *
227 * The run queue must be locked.
228 */
229 thread_t
run_queue_peek(run_queue_t rq)230 run_queue_peek(
231 run_queue_t rq)
232 {
233 if (rq->count > 0) {
234 circle_queue_t queue = &rq->queues[rq->highq];
235 thread_t thread = cqe_queue_first(queue, struct thread, runq_links);
236 return thread;
237 } else {
238 return THREAD_NULL;
239 }
240 }
241
242 uint32_t sched_run_buckets[TH_BUCKET_MAX];
243 unsigned sched_tick = 0;
244 int8_t sched_load_shifts[NRQS];
245
246 #define DEFAULT_PREEMPTION_RATE 100 /* (1/s) */
247 int default_preemption_rate = DEFAULT_PREEMPTION_RATE;
248 #define DEFAULT_BG_PREEMPTION_RATE 400 /* (1/s) */
249 static int default_bg_preemption_rate = DEFAULT_BG_PREEMPTION_RATE;
250
251 uint32_t std_quantum;
252 uint32_t min_std_quantum;
253 static uint32_t bg_quantum;
254
255 uint32_t std_quantum_us;
256 static uint32_t bg_quantum_us;
257
258 uint32_t default_timeshare_constraint;
259 uint32_t sched_fixed_shift;
260
261 void
sched_timeshare_init(void)262 sched_timeshare_init(void)
263 {
264 /*
265 * Calculate the timeslicing quantum
266 * in us.
267 */
268 if (default_preemption_rate < 1) {
269 default_preemption_rate = DEFAULT_PREEMPTION_RATE;
270 }
271 std_quantum_us = (1000 * 1000) / default_preemption_rate;
272
273 if (default_bg_preemption_rate < 1) {
274 default_bg_preemption_rate = DEFAULT_BG_PREEMPTION_RATE;
275 }
276 bg_quantum_us = (1000 * 1000) / default_bg_preemption_rate;
277 }
278
279 void
sched_timeshare_timebase_init(void)280 sched_timeshare_timebase_init(void)
281 {
282 uint64_t abstime;
283 uint32_t shift;
284
285 /* standard timeslicing quantum */
286 clock_interval_to_absolutetime_interval(
287 std_quantum_us, NSEC_PER_USEC, &abstime);
288 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
289 std_quantum = (uint32_t)abstime;
290
291 /* smallest remaining quantum (250 us) */
292 clock_interval_to_absolutetime_interval(250, NSEC_PER_USEC, &abstime);
293 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
294 min_std_quantum = (uint32_t)abstime;
295
296 /* quantum for background tasks */
297 clock_interval_to_absolutetime_interval(
298 bg_quantum_us, NSEC_PER_USEC, &abstime);
299 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
300 bg_quantum = (uint32_t)abstime;
301
302 /* scheduler tick interval */
303 clock_interval_to_absolutetime_interval(USEC_PER_SEC >> SCHED_TICK_SHIFT,
304 NSEC_PER_USEC, &abstime);
305 assert((abstime >> 32) == 0 && (uint32_t)abstime != 0);
306
307 /*
308 * Compute conversion factor from usage to
309 * timesharing priorities with 5/8 ** n aging.
310 */
311 abstime = (abstime * 5) / 3;
312 for (shift = 0; abstime > BASEPRI_DEFAULT; ++shift) {
313 abstime >>= 1;
314 }
315 sched_fixed_shift = shift;
316
317 default_timeshare_constraint = std_quantum;
318 }
319