]> git.saurik.com Git - apple/xnu.git/blob - osfmk/kern/sched_dualq.c
xnu-4570.31.3.tar.gz
[apple/xnu.git] / osfmk / kern / sched_dualq.c
1 /*
2 * Copyright (c) 2013 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 #include <mach/mach_types.h>
30 #include <mach/machine.h>
31
32 #include <machine/machine_routines.h>
33 #include <machine/sched_param.h>
34 #include <machine/machine_cpu.h>
35
36 #include <kern/kern_types.h>
37 #include <kern/debug.h>
38 #include <kern/machine.h>
39 #include <kern/misc_protos.h>
40 #include <kern/processor.h>
41 #include <kern/queue.h>
42 #include <kern/sched.h>
43 #include <kern/sched_prim.h>
44 #include <kern/task.h>
45 #include <kern/thread.h>
46
47 #include <sys/kdebug.h>
48
49 static void
50 sched_dualq_init(void);
51
52 static thread_t
53 sched_dualq_steal_thread(processor_set_t pset);
54
55 static void
56 sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context);
57
58 static boolean_t
59 sched_dualq_processor_enqueue(processor_t processor, thread_t thread, integer_t options);
60
61 static boolean_t
62 sched_dualq_processor_queue_remove(processor_t processor, thread_t thread);
63
64 static ast_t
65 sched_dualq_processor_csw_check(processor_t processor);
66
67 static boolean_t
68 sched_dualq_processor_queue_has_priority(processor_t processor, int priority, boolean_t gte);
69
70 static int
71 sched_dualq_runq_count(processor_t processor);
72
73 static boolean_t
74 sched_dualq_processor_queue_empty(processor_t processor);
75
76 static uint64_t
77 sched_dualq_runq_stats_count_sum(processor_t processor);
78
79 static int
80 sched_dualq_processor_bound_count(processor_t processor);
81
82 static void
83 sched_dualq_pset_init(processor_set_t pset);
84
85 static void
86 sched_dualq_processor_init(processor_t processor);
87
88 static thread_t
89 sched_dualq_choose_thread(processor_t processor, int priority, ast_t reason);
90
91 static void
92 sched_dualq_processor_queue_shutdown(processor_t processor);
93
94 static sched_mode_t
95 sched_dualq_initial_thread_sched_mode(task_t parent_task);
96
97 const struct sched_dispatch_table sched_dualq_dispatch = {
98 .sched_name = "dualq",
99 .init = sched_dualq_init,
100 .timebase_init = sched_timeshare_timebase_init,
101 .processor_init = sched_dualq_processor_init,
102 .pset_init = sched_dualq_pset_init,
103 .maintenance_continuation = sched_timeshare_maintenance_continue,
104 .choose_thread = sched_dualq_choose_thread,
105 .steal_thread_enabled = TRUE,
106 .steal_thread = sched_dualq_steal_thread,
107 .compute_timeshare_priority = sched_compute_timeshare_priority,
108 .choose_processor = choose_processor,
109 .processor_enqueue = sched_dualq_processor_enqueue,
110 .processor_queue_shutdown = sched_dualq_processor_queue_shutdown,
111 .processor_queue_remove = sched_dualq_processor_queue_remove,
112 .processor_queue_empty = sched_dualq_processor_queue_empty,
113 .priority_is_urgent = priority_is_urgent,
114 .processor_csw_check = sched_dualq_processor_csw_check,
115 .processor_queue_has_priority = sched_dualq_processor_queue_has_priority,
116 .initial_quantum_size = sched_timeshare_initial_quantum_size,
117 .initial_thread_sched_mode = sched_dualq_initial_thread_sched_mode,
118 .can_update_priority = can_update_priority,
119 .update_priority = update_priority,
120 .lightweight_update_priority = lightweight_update_priority,
121 .quantum_expire = sched_default_quantum_expire,
122 .processor_runq_count = sched_dualq_runq_count,
123 .processor_runq_stats_count_sum = sched_dualq_runq_stats_count_sum,
124 .processor_bound_count = sched_dualq_processor_bound_count,
125 .thread_update_scan = sched_dualq_thread_update_scan,
126 .direct_dispatch_to_idle_processors = FALSE,
127 .multiple_psets_enabled = TRUE,
128 .sched_groups_enabled = FALSE,
129 .avoid_processor_enabled = FALSE,
130 .thread_avoid_processor = NULL,
131 .processor_balance = sched_SMT_balance,
132
133 .rt_runq = sched_rtglobal_runq,
134 .rt_init = sched_rtglobal_init,
135 .rt_queue_shutdown = sched_rtglobal_queue_shutdown,
136 .rt_runq_scan = sched_rtglobal_runq_scan,
137 .rt_runq_count_sum = sched_rtglobal_runq_count_sum,
138
139 .qos_max_parallelism = sched_qos_max_parallelism,
140 .check_spill = sched_check_spill,
141 .ipi_policy = sched_ipi_policy,
142 .thread_should_yield = sched_thread_should_yield,
143 };
144
145 __attribute__((always_inline))
146 static inline run_queue_t dualq_main_runq(processor_t processor)
147 {
148 return &processor->processor_set->pset_runq;
149 }
150
151 __attribute__((always_inline))
152 static inline run_queue_t dualq_bound_runq(processor_t processor)
153 {
154 return &processor->runq;
155 }
156
157 __attribute__((always_inline))
158 static inline run_queue_t dualq_runq_for_thread(processor_t processor, thread_t thread)
159 {
160 if (thread->bound_processor == PROCESSOR_NULL) {
161 return dualq_main_runq(processor);
162 } else {
163 assert(thread->bound_processor == processor);
164 return dualq_bound_runq(processor);
165 }
166 }
167
168 static sched_mode_t
169 sched_dualq_initial_thread_sched_mode(task_t parent_task)
170 {
171 if (parent_task == kernel_task)
172 return TH_MODE_FIXED;
173 else
174 return TH_MODE_TIMESHARE;
175 }
176
177 static void
178 sched_dualq_processor_init(processor_t processor)
179 {
180 run_queue_init(&processor->runq);
181 }
182
183 static void
184 sched_dualq_pset_init(processor_set_t pset)
185 {
186 run_queue_init(&pset->pset_runq);
187 }
188
189 static void
190 sched_dualq_init(void)
191 {
192 sched_timeshare_init();
193 }
194
195 static thread_t
196 sched_dualq_choose_thread(
197 processor_t processor,
198 int priority,
199 __unused ast_t reason)
200 {
201 run_queue_t main_runq = dualq_main_runq(processor);
202 run_queue_t bound_runq = dualq_bound_runq(processor);
203 run_queue_t chosen_runq;
204
205 if (bound_runq->highq < priority &&
206 main_runq->highq < priority)
207 return THREAD_NULL;
208
209 if (bound_runq->count && main_runq->count) {
210 if (bound_runq->highq >= main_runq->highq) {
211 chosen_runq = bound_runq;
212 } else {
213 chosen_runq = main_runq;
214 }
215 } else if (bound_runq->count) {
216 chosen_runq = bound_runq;
217 } else if (main_runq->count) {
218 chosen_runq = main_runq;
219 } else {
220 return (THREAD_NULL);
221 }
222
223 return run_queue_dequeue(chosen_runq, SCHED_HEADQ);
224 }
225
226 static boolean_t
227 sched_dualq_processor_enqueue(
228 processor_t processor,
229 thread_t thread,
230 integer_t options)
231 {
232 run_queue_t rq = dualq_runq_for_thread(processor, thread);
233 boolean_t result;
234
235 result = run_queue_enqueue(rq, thread, options);
236 thread->runq = processor;
237
238 return (result);
239 }
240
241 static boolean_t
242 sched_dualq_processor_queue_empty(processor_t processor)
243 {
244 return dualq_main_runq(processor)->count == 0 &&
245 dualq_bound_runq(processor)->count == 0;
246 }
247
248 static ast_t
249 sched_dualq_processor_csw_check(processor_t processor)
250 {
251 boolean_t has_higher;
252 int pri;
253
254 run_queue_t main_runq = dualq_main_runq(processor);
255 run_queue_t bound_runq = dualq_bound_runq(processor);
256
257 assert(processor->active_thread != NULL);
258
259 pri = MAX(main_runq->highq, bound_runq->highq);
260
261 if (processor->first_timeslice) {
262 has_higher = (pri > processor->current_pri);
263 } else {
264 has_higher = (pri >= processor->current_pri);
265 }
266
267 if (has_higher) {
268 if (main_runq->urgency > 0)
269 return (AST_PREEMPT | AST_URGENT);
270
271 if (bound_runq->urgency > 0)
272 return (AST_PREEMPT | AST_URGENT);
273
274 return AST_PREEMPT;
275 }
276
277 return AST_NONE;
278 }
279
280 static boolean_t
281 sched_dualq_processor_queue_has_priority(processor_t processor,
282 int priority,
283 boolean_t gte)
284 {
285 run_queue_t main_runq = dualq_main_runq(processor);
286 run_queue_t bound_runq = dualq_bound_runq(processor);
287
288 int qpri = MAX(main_runq->highq, bound_runq->highq);
289
290 if (gte)
291 return qpri >= priority;
292 else
293 return qpri > priority;
294 }
295
296 static int
297 sched_dualq_runq_count(processor_t processor)
298 {
299 return dualq_main_runq(processor)->count + dualq_bound_runq(processor)->count;
300 }
301
302 static uint64_t
303 sched_dualq_runq_stats_count_sum(processor_t processor)
304 {
305 uint64_t bound_sum = dualq_bound_runq(processor)->runq_stats.count_sum;
306
307 if (processor->cpu_id == processor->processor_set->cpu_set_low)
308 return bound_sum + dualq_main_runq(processor)->runq_stats.count_sum;
309 else
310 return bound_sum;
311 }
312 static int
313 sched_dualq_processor_bound_count(processor_t processor)
314 {
315 return dualq_bound_runq(processor)->count;
316 }
317
318 static void
319 sched_dualq_processor_queue_shutdown(processor_t processor)
320 {
321 processor_set_t pset = processor->processor_set;
322 run_queue_t rq = dualq_main_runq(processor);
323 thread_t thread;
324 queue_head_t tqueue;
325
326 /* We only need to migrate threads if this is the last active processor in the pset */
327 if (pset->online_processor_count > 0) {
328 pset_unlock(pset);
329 return;
330 }
331
332 queue_init(&tqueue);
333
334 while (rq->count > 0) {
335 thread = run_queue_dequeue(rq, SCHED_HEADQ);
336 enqueue_tail(&tqueue, &thread->runq_links);
337 }
338
339 pset_unlock(pset);
340
341 qe_foreach_element_safe(thread, &tqueue, runq_links) {
342
343 remqueue(&thread->runq_links);
344
345 thread_lock(thread);
346
347 thread_setrun(thread, SCHED_TAILQ);
348
349 thread_unlock(thread);
350 }
351 }
352
353 static boolean_t
354 sched_dualq_processor_queue_remove(
355 processor_t processor,
356 thread_t thread)
357 {
358 run_queue_t rq;
359 processor_set_t pset = processor->processor_set;
360
361 pset_lock(pset);
362
363 rq = dualq_runq_for_thread(processor, thread);
364
365 if (processor == thread->runq) {
366 /*
367 * Thread is on a run queue and we have a lock on
368 * that run queue.
369 */
370 run_queue_remove(rq, thread);
371 }
372 else {
373 /*
374 * The thread left the run queue before we could
375 * lock the run queue.
376 */
377 assert(thread->runq == PROCESSOR_NULL);
378 processor = PROCESSOR_NULL;
379 }
380
381 pset_unlock(pset);
382
383 return (processor != PROCESSOR_NULL);
384 }
385
386 static thread_t
387 sched_dualq_steal_thread(processor_set_t pset)
388 {
389 processor_set_t nset, cset = pset;
390 thread_t thread;
391
392 do {
393 if (cset->pset_runq.count > 0) {
394 thread = run_queue_dequeue(&cset->pset_runq, SCHED_HEADQ);
395 pset_unlock(cset);
396 return (thread);
397 }
398
399 nset = next_pset(cset);
400
401 if (nset != pset) {
402 pset_unlock(cset);
403
404 cset = nset;
405 pset_lock(cset);
406 }
407 } while (nset != pset);
408
409 pset_unlock(cset);
410
411 return (THREAD_NULL);
412 }
413
414 static void
415 sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context)
416 {
417 boolean_t restart_needed = FALSE;
418 processor_t processor = processor_list;
419 processor_set_t pset;
420 thread_t thread;
421 spl_t s;
422
423 /*
424 * We update the threads associated with each processor (bound and idle threads)
425 * and then update the threads in each pset runqueue.
426 */
427
428 do {
429 do {
430 pset = processor->processor_set;
431
432 s = splsched();
433 pset_lock(pset);
434
435 restart_needed = runq_scan(dualq_bound_runq(processor), scan_context);
436
437 pset_unlock(pset);
438 splx(s);
439
440 if (restart_needed)
441 break;
442
443 thread = processor->idle_thread;
444 if (thread != THREAD_NULL && thread->sched_stamp != sched_tick) {
445 if (thread_update_add_thread(thread) == FALSE) {
446 restart_needed = TRUE;
447 break;
448 }
449 }
450 } while ((processor = processor->processor_list) != NULL);
451
452 /* Ok, we now have a collection of candidates -- fix them. */
453 thread_update_process_threads();
454
455 } while (restart_needed);
456
457 pset = &pset0;
458
459 do {
460 do {
461 s = splsched();
462 pset_lock(pset);
463
464 restart_needed = runq_scan(&pset->pset_runq, scan_context);
465
466 pset_unlock(pset);
467 splx(s);
468
469 if (restart_needed)
470 break;
471 } while ((pset = pset->pset_list) != NULL);
472
473 /* Ok, we now have a collection of candidates -- fix them. */
474 thread_update_process_threads();
475
476 } while (restart_needed);
477 }
478
479