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
49static void
50sched_dualq_init(void);
51
52static thread_t
53sched_dualq_steal_thread(processor_set_t pset);
54
55static void
56sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context);
57
58static boolean_t
59sched_dualq_processor_enqueue(processor_t processor, thread_t thread,
60 sched_options_t options);
61
62static boolean_t
63sched_dualq_processor_queue_remove(processor_t processor, thread_t thread);
64
65static ast_t
66sched_dualq_processor_csw_check(processor_t processor);
67
68static boolean_t
69sched_dualq_processor_queue_has_priority(processor_t processor, int priority, boolean_t gte);
70
71static int
72sched_dualq_runq_count(processor_t processor);
73
74static boolean_t
75sched_dualq_processor_queue_empty(processor_t processor);
76
77static uint64_t
78sched_dualq_runq_stats_count_sum(processor_t processor);
79
80static int
81sched_dualq_processor_bound_count(processor_t processor);
82
83static void
84sched_dualq_pset_init(processor_set_t pset);
85
86static void
87sched_dualq_processor_init(processor_t processor);
88
89static thread_t
90sched_dualq_choose_thread(processor_t processor, int priority, ast_t reason);
91
92static void
93sched_dualq_processor_queue_shutdown(processor_t processor);
94
95static sched_mode_t
96sched_dualq_initial_thread_sched_mode(task_t parent_task);
97
98static bool
99sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread, __unused ast_t reason);
100
101const struct sched_dispatch_table sched_dualq_dispatch = {
102 .sched_name = "dualq",
103 .init = sched_dualq_init,
104 .timebase_init = sched_timeshare_timebase_init,
105 .processor_init = sched_dualq_processor_init,
106 .pset_init = sched_dualq_pset_init,
107 .maintenance_continuation = sched_timeshare_maintenance_continue,
108 .choose_thread = sched_dualq_choose_thread,
109 .steal_thread_enabled = sched_steal_thread_enabled,
110 .steal_thread = sched_dualq_steal_thread,
111 .compute_timeshare_priority = sched_compute_timeshare_priority,
112 .choose_node = sched_choose_node,
113 .choose_processor = choose_processor,
114 .processor_enqueue = sched_dualq_processor_enqueue,
115 .processor_queue_shutdown = sched_dualq_processor_queue_shutdown,
116 .processor_queue_remove = sched_dualq_processor_queue_remove,
117 .processor_queue_empty = sched_dualq_processor_queue_empty,
118 .priority_is_urgent = priority_is_urgent,
119 .processor_csw_check = sched_dualq_processor_csw_check,
120 .processor_queue_has_priority = sched_dualq_processor_queue_has_priority,
121 .initial_quantum_size = sched_timeshare_initial_quantum_size,
122 .initial_thread_sched_mode = sched_dualq_initial_thread_sched_mode,
123 .can_update_priority = can_update_priority,
124 .update_priority = update_priority,
125 .lightweight_update_priority = lightweight_update_priority,
126 .quantum_expire = sched_default_quantum_expire,
127 .processor_runq_count = sched_dualq_runq_count,
128 .processor_runq_stats_count_sum = sched_dualq_runq_stats_count_sum,
129 .processor_bound_count = sched_dualq_processor_bound_count,
130 .thread_update_scan = sched_dualq_thread_update_scan,
131 .multiple_psets_enabled = TRUE,
132 .sched_groups_enabled = FALSE,
133 .avoid_processor_enabled = TRUE,
134 .thread_avoid_processor = sched_dualq_thread_avoid_processor,
135 .processor_balance = sched_SMT_balance,
136
137 .rt_runq = sched_rtlocal_runq,
138 .rt_init = sched_rtlocal_init,
139 .rt_queue_shutdown = sched_rtlocal_queue_shutdown,
140 .rt_runq_scan = sched_rtlocal_runq_scan,
141 .rt_runq_count_sum = sched_rtlocal_runq_count_sum,
142 .rt_steal_thread = sched_rtlocal_steal_thread,
143
144 .qos_max_parallelism = sched_qos_max_parallelism,
145 .check_spill = sched_check_spill,
146 .ipi_policy = sched_ipi_policy,
147 .thread_should_yield = sched_thread_should_yield,
148 .run_count_incr = sched_smt_run_incr,
149 .run_count_decr = sched_smt_run_decr,
150 .update_thread_bucket = sched_smt_update_thread_bucket,
151 .pset_made_schedulable = sched_pset_made_schedulable,
152 .cpu_init_completed = NULL,
153 .thread_eligible_for_pset = NULL,
154};
155
156__attribute__((always_inline))
157static inline run_queue_t
158dualq_main_runq(processor_t processor)
159{
160 return &processor->processor_set->pset_runq;
161}
162
163__attribute__((always_inline))
164static inline run_queue_t
165dualq_bound_runq(processor_t processor)
166{
167 return &processor->runq;
168}
169
170__attribute__((always_inline))
171static inline run_queue_t
172dualq_runq_for_thread(processor_t processor, thread_t thread)
173{
174 if (thread->bound_processor == PROCESSOR_NULL) {
175 return dualq_main_runq(processor);
176 } else {
177 assert(thread->bound_processor == processor);
178 return dualq_bound_runq(processor);
179 }
180}
181
182static sched_mode_t
183sched_dualq_initial_thread_sched_mode(task_t parent_task)
184{
185 if (parent_task == kernel_task) {
186 return TH_MODE_FIXED;
187 } else {
188 return TH_MODE_TIMESHARE;
189 }
190}
191
192static void
193sched_dualq_processor_init(processor_t processor)
194{
195 run_queue_init(runq: &processor->runq);
196}
197
198static void
199sched_dualq_pset_init(processor_set_t pset)
200{
201 run_queue_init(runq: &pset->pset_runq);
202}
203
204extern int sched_allow_NO_SMT_threads;
205static void
206sched_dualq_init(void)
207{
208 sched_timeshare_init();
209
210 if (PE_parse_boot_argn(arg_string: "disable_NO_SMT_threads", NULL, max_arg: 0)) {
211 sched_allow_NO_SMT_threads = 0;
212 }
213}
214
215static thread_t
216sched_dualq_choose_thread(
217 processor_t processor,
218 int priority,
219 __unused ast_t reason)
220{
221 run_queue_t main_runq = dualq_main_runq(processor);
222 run_queue_t bound_runq = dualq_bound_runq(processor);
223 run_queue_t chosen_runq;
224
225 if (bound_runq->highq < priority &&
226 main_runq->highq < priority) {
227 return THREAD_NULL;
228 }
229
230 if (bound_runq->count && main_runq->count) {
231 if (bound_runq->highq >= main_runq->highq) {
232 chosen_runq = bound_runq;
233 } else {
234 chosen_runq = main_runq;
235 }
236 } else if (bound_runq->count) {
237 chosen_runq = bound_runq;
238 } else if (main_runq->count) {
239 chosen_runq = main_runq;
240 } else {
241 return THREAD_NULL;
242 }
243
244 if (chosen_runq == bound_runq) {
245 return run_queue_dequeue(runq: chosen_runq, options: SCHED_HEADQ);
246 }
247
248 if (processor->is_SMT) {
249 thread_t potential_thread = run_queue_peek(runq: chosen_runq);
250 if (potential_thread == THREAD_NULL) {
251 return THREAD_NULL;
252 }
253 if (processor->processor_primary != processor) {
254 /*
255 * Secondary processor may not run a NO_SMT thread,
256 * nor any thread if the primary is running a NO_SMT thread.
257 */
258 if (thread_no_smt(thread: potential_thread)) {
259 processor->must_idle = true;
260 return THREAD_NULL;
261 }
262 processor_t primary = processor->processor_primary;
263 if (primary->state == PROCESSOR_RUNNING) {
264 if (processor_active_thread_no_smt(processor: primary)) {
265 processor->must_idle = true;
266 return THREAD_NULL;
267 }
268 }
269 } else if (processor->processor_secondary != PROCESSOR_NULL) {
270 processor_t secondary = processor->processor_secondary;
271 /*
272 * Primary processor may not run a NO_SMT thread if
273 * its secondary is running a bound thread.
274 */
275 if (secondary->state == PROCESSOR_RUNNING) {
276 if (thread_no_smt(thread: potential_thread) && secondary->current_is_bound) {
277 processor->must_idle = true;
278 return THREAD_NULL;
279 }
280 }
281 }
282 }
283
284 return run_queue_dequeue(runq: chosen_runq, options: SCHED_HEADQ);
285}
286
287static boolean_t
288sched_dualq_processor_enqueue(
289 processor_t processor,
290 thread_t thread,
291 sched_options_t options)
292{
293 run_queue_t rq = dualq_runq_for_thread(processor, thread);
294 boolean_t result;
295
296 result = run_queue_enqueue(runq: rq, thread, options);
297 thread_set_runq_locked(thread, new_runq: processor);
298
299 return result;
300}
301
302static boolean_t
303sched_dualq_processor_queue_empty(processor_t processor)
304{
305 return dualq_main_runq(processor)->count == 0 &&
306 dualq_bound_runq(processor)->count == 0;
307}
308
309static ast_t
310sched_dualq_processor_csw_check(processor_t processor)
311{
312 boolean_t has_higher;
313 int pri;
314
315 if (sched_dualq_thread_avoid_processor(processor, thread: current_thread(), AST_NONE)) {
316 return AST_PREEMPT | AST_URGENT;
317 }
318
319 run_queue_t main_runq = dualq_main_runq(processor);
320 run_queue_t bound_runq = dualq_bound_runq(processor);
321
322 assert(processor->active_thread != NULL);
323
324 pri = MAX(main_runq->highq, bound_runq->highq);
325
326 if (processor->first_timeslice) {
327 has_higher = (pri > processor->current_pri);
328 } else {
329 has_higher = (pri >= processor->current_pri);
330 }
331
332 if (has_higher) {
333 if (main_runq->urgency > 0) {
334 return AST_PREEMPT | AST_URGENT;
335 }
336
337 if (bound_runq->urgency > 0) {
338 return AST_PREEMPT | AST_URGENT;
339 }
340
341 return AST_PREEMPT;
342 }
343
344 return AST_NONE;
345}
346
347static boolean_t
348sched_dualq_processor_queue_has_priority(processor_t processor,
349 int priority,
350 boolean_t gte)
351{
352 run_queue_t main_runq = dualq_main_runq(processor);
353 run_queue_t bound_runq = dualq_bound_runq(processor);
354
355 int qpri = MAX(main_runq->highq, bound_runq->highq);
356
357 if (gte) {
358 return qpri >= priority;
359 } else {
360 return qpri > priority;
361 }
362}
363
364static int
365sched_dualq_runq_count(processor_t processor)
366{
367 return dualq_main_runq(processor)->count + dualq_bound_runq(processor)->count;
368}
369
370static uint64_t
371sched_dualq_runq_stats_count_sum(processor_t processor)
372{
373 uint64_t bound_sum = dualq_bound_runq(processor)->runq_stats.count_sum;
374
375 if (processor->cpu_id == processor->processor_set->cpu_set_low) {
376 return bound_sum + dualq_main_runq(processor)->runq_stats.count_sum;
377 } else {
378 return bound_sum;
379 }
380}
381static int
382sched_dualq_processor_bound_count(processor_t processor)
383{
384 return dualq_bound_runq(processor)->count;
385}
386
387static void
388sched_dualq_processor_queue_shutdown(processor_t processor)
389{
390 processor_set_t pset = processor->processor_set;
391 run_queue_t rq = dualq_main_runq(processor);
392 thread_t thread;
393 queue_head_t tqueue;
394
395 /* We only need to migrate threads if this is the last active processor in the pset */
396 if (pset->online_processor_count > 0) {
397 pset_unlock(pset);
398 return;
399 }
400
401 queue_init(&tqueue);
402
403 while (rq->count > 0) {
404 thread = run_queue_dequeue(runq: rq, options: SCHED_HEADQ);
405 enqueue_tail(que: &tqueue, elt: &thread->runq_links);
406 }
407
408 pset_unlock(pset);
409
410 qe_foreach_element_safe(thread, &tqueue, runq_links) {
411 remqueue(elt: &thread->runq_links);
412
413 thread_lock(thread);
414
415 thread_setrun(thread, options: SCHED_TAILQ);
416
417 thread_unlock(thread);
418 }
419}
420
421static boolean_t
422sched_dualq_processor_queue_remove(
423 processor_t processor,
424 thread_t thread)
425{
426 run_queue_t rq;
427 processor_set_t pset = processor->processor_set;
428
429 pset_lock(pset);
430
431 rq = dualq_runq_for_thread(processor, thread);
432
433 if (processor == thread_get_runq_locked(thread)) {
434 /*
435 * Thread is on a run queue and we have a lock on
436 * that run queue.
437 */
438 run_queue_remove(runq: rq, thread);
439 } else {
440 /*
441 * The thread left the run queue before we could
442 * lock the run queue.
443 */
444 thread_assert_runq_null(thread);
445 processor = PROCESSOR_NULL;
446 }
447
448 pset_unlock(pset);
449
450 return processor != PROCESSOR_NULL;
451}
452
453static thread_t
454sched_dualq_steal_thread(processor_set_t pset)
455{
456 processor_set_t cset = pset;
457 processor_set_t nset = next_pset(pset: cset);
458 thread_t thread;
459
460 /* Secondary processors on SMT systems never steal */
461 assert(current_processor()->processor_primary == current_processor());
462
463 while (nset != pset) {
464 pset_unlock(cset);
465 cset = nset;
466 pset_lock(cset);
467
468 if (pset_has_stealable_threads(pset: cset)) {
469 /* Need task_restrict logic here */
470 thread = run_queue_dequeue(runq: &cset->pset_runq, options: SCHED_HEADQ);
471 pset_unlock(cset);
472 return thread;
473 }
474
475 nset = next_pset(pset: cset);
476 }
477
478 pset_unlock(cset);
479
480 return THREAD_NULL;
481}
482
483static void
484sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context)
485{
486 boolean_t restart_needed = FALSE;
487 processor_t processor = processor_list;
488 processor_set_t pset;
489 thread_t thread;
490 spl_t s;
491
492 /*
493 * We update the threads associated with each processor (bound and idle threads)
494 * and then update the threads in each pset runqueue.
495 */
496
497 do {
498 do {
499 pset = processor->processor_set;
500
501 s = splsched();
502 pset_lock(pset);
503
504 restart_needed = runq_scan(runq: dualq_bound_runq(processor), scan_context);
505
506 pset_unlock(pset);
507 splx(s);
508
509 if (restart_needed) {
510 break;
511 }
512
513 thread = processor->idle_thread;
514 if (thread != THREAD_NULL && thread->sched_stamp != sched_tick) {
515 if (thread_update_add_thread(thread) == FALSE) {
516 restart_needed = TRUE;
517 break;
518 }
519 }
520 } while ((processor = processor->processor_list) != NULL);
521
522 /* Ok, we now have a collection of candidates -- fix them. */
523 thread_update_process_threads();
524 } while (restart_needed);
525
526 pset = &pset0;
527
528 do {
529 do {
530 s = splsched();
531 pset_lock(pset);
532
533 restart_needed = runq_scan(runq: &pset->pset_runq, scan_context);
534
535 pset_unlock(pset);
536 splx(s);
537
538 if (restart_needed) {
539 break;
540 }
541 } while ((pset = pset->pset_list) != NULL);
542
543 /* Ok, we now have a collection of candidates -- fix them. */
544 thread_update_process_threads();
545 } while (restart_needed);
546}
547
548extern int sched_allow_rt_smt;
549
550/* Return true if this thread should not continue running on this processor */
551static bool
552sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread, __unused ast_t reason)
553{
554 if (thread->bound_processor == processor) {
555 /* Thread is bound here */
556 return false;
557 }
558
559 if (processor->processor_primary != processor) {
560 /*
561 * This is a secondary SMT processor. If the primary is running
562 * a realtime thread, only allow realtime threads on the secondary.
563 */
564 processor_t primary = processor->processor_primary;
565 if ((primary->current_pri >= BASEPRI_RTQUEUES) && ((thread->sched_pri < BASEPRI_RTQUEUES) || !sched_allow_rt_smt)) {
566 return true;
567 }
568
569 /* NO_SMT threads are not allowed on secondary processors */
570 if (thread_no_smt(thread)) {
571 return true;
572 }
573
574 if (primary->state == PROCESSOR_RUNNING) {
575 if (processor_active_thread_no_smt(processor: primary)) {
576 /* No threads allowed on secondary if primary has NO_SMT */
577 return true;
578 }
579 }
580 }
581
582 if (processor->processor_secondary != PROCESSOR_NULL) {
583 /*
584 * This is a primary SMT processor. If the secondary is running
585 * a bound thread, the primary may not run a NO_SMT thread.
586 */
587 processor_t secondary = processor->processor_secondary;
588
589 if (secondary->state == PROCESSOR_RUNNING) {
590 if (secondary->current_is_bound && thread_no_smt(thread)) {
591 return true;
592 }
593 }
594 }
595
596 return false;
597}
598