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