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);
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 };
164
165 __attribute__((always_inline))
166 static inline run_queue_t
dualq_main_runq(processor_t processor)167 dualq_main_runq(processor_t processor)
168 {
169 return &processor->processor_set->pset_runq;
170 }
171
172 __attribute__((always_inline))
173 static inline run_queue_t
dualq_bound_runq(processor_t processor)174 dualq_bound_runq(processor_t processor)
175 {
176 return &processor->runq;
177 }
178
179 __attribute__((always_inline))
180 static inline run_queue_t
dualq_runq_for_thread(processor_t processor,thread_t thread)181 dualq_runq_for_thread(processor_t processor, thread_t thread)
182 {
183 if (thread->bound_processor == PROCESSOR_NULL) {
184 return dualq_main_runq(processor);
185 } else {
186 assert(thread->bound_processor == processor);
187 return dualq_bound_runq(processor);
188 }
189 }
190
191 static sched_mode_t
sched_dualq_initial_thread_sched_mode(task_t parent_task)192 sched_dualq_initial_thread_sched_mode(task_t parent_task)
193 {
194 if (parent_task == kernel_task) {
195 return TH_MODE_FIXED;
196 } else {
197 return TH_MODE_TIMESHARE;
198 }
199 }
200
201 static void
sched_dualq_processor_init(processor_t processor)202 sched_dualq_processor_init(processor_t processor)
203 {
204 run_queue_init(&processor->runq);
205 }
206
207 static void
sched_dualq_pset_init(processor_set_t pset)208 sched_dualq_pset_init(processor_set_t pset)
209 {
210 run_queue_init(&pset->pset_runq);
211 }
212
213 extern int sched_allow_NO_SMT_threads;
214 static void
sched_dualq_init(void)215 sched_dualq_init(void)
216 {
217 sched_timeshare_init();
218
219 if (PE_parse_boot_argn("disable_NO_SMT_threads", NULL, 0)) {
220 sched_allow_NO_SMT_threads = 0;
221 }
222 }
223
224 static thread_t
sched_dualq_choose_thread(processor_t processor,int priority,__unused thread_t prev_thread,__unused ast_t reason)225 sched_dualq_choose_thread(
226 processor_t processor,
227 int priority,
228 __unused thread_t prev_thread,
229 __unused ast_t reason)
230 {
231 run_queue_t main_runq = dualq_main_runq(processor);
232 run_queue_t bound_runq = dualq_bound_runq(processor);
233 run_queue_t chosen_runq;
234
235 if (bound_runq->highq < priority &&
236 main_runq->highq < priority) {
237 return THREAD_NULL;
238 }
239
240 if (bound_runq->count && main_runq->count) {
241 if (bound_runq->highq >= main_runq->highq) {
242 chosen_runq = bound_runq;
243 } else {
244 chosen_runq = main_runq;
245 }
246 } else if (bound_runq->count) {
247 chosen_runq = bound_runq;
248 } else if (main_runq->count) {
249 chosen_runq = main_runq;
250 } else {
251 return THREAD_NULL;
252 }
253
254 if (chosen_runq == bound_runq) {
255 return run_queue_dequeue(chosen_runq, SCHED_HEADQ);
256 }
257
258 #if CONFIG_SCHED_SMT
259 if (processor->is_SMT) {
260 thread_t potential_thread = run_queue_peek(chosen_runq);
261 if (potential_thread == THREAD_NULL) {
262 return THREAD_NULL;
263 }
264 if (processor->processor_primary != processor) {
265 /*
266 * Secondary processor may not run a NO_SMT thread,
267 * nor any thread if the primary is running a NO_SMT thread.
268 */
269 if (thread_no_smt(potential_thread)) {
270 processor->must_idle = true;
271 return THREAD_NULL;
272 }
273 processor_t primary = processor->processor_primary;
274 if (primary->state == PROCESSOR_RUNNING) {
275 if (processor_active_thread_no_smt(primary)) {
276 processor->must_idle = true;
277 return THREAD_NULL;
278 }
279 }
280 } else if (processor->processor_secondary != PROCESSOR_NULL) {
281 processor_t secondary = processor->processor_secondary;
282 /*
283 * Primary processor may not run a NO_SMT thread if
284 * its secondary is running a bound thread.
285 */
286 if (secondary->state == PROCESSOR_RUNNING) {
287 if (thread_no_smt(potential_thread) && secondary->current_is_bound) {
288 processor->must_idle = true;
289 return THREAD_NULL;
290 }
291 }
292 }
293 }
294 #endif /* CONFIG_SCHED_SMT */
295
296 return run_queue_dequeue(chosen_runq, SCHED_HEADQ);
297 }
298
299 static boolean_t
sched_dualq_processor_enqueue(processor_t processor,thread_t thread,sched_options_t options)300 sched_dualq_processor_enqueue(
301 processor_t processor,
302 thread_t thread,
303 sched_options_t options)
304 {
305 run_queue_t rq = dualq_runq_for_thread(processor, thread);
306 boolean_t result;
307
308 result = run_queue_enqueue(rq, thread, options);
309 thread_set_runq_locked(thread, processor);
310
311 return result;
312 }
313
314 static boolean_t
sched_dualq_processor_queue_empty(processor_t processor)315 sched_dualq_processor_queue_empty(processor_t processor)
316 {
317 return dualq_main_runq(processor)->count == 0 &&
318 dualq_bound_runq(processor)->count == 0;
319 }
320
321 static ast_t
sched_dualq_processor_csw_check(processor_t processor)322 sched_dualq_processor_csw_check(processor_t processor)
323 {
324 boolean_t has_higher;
325 int pri;
326
327 if (sched_dualq_thread_avoid_processor(processor, current_thread(), AST_NONE)) {
328 return AST_PREEMPT | AST_URGENT;
329 }
330
331 run_queue_t main_runq = dualq_main_runq(processor);
332 run_queue_t bound_runq = dualq_bound_runq(processor);
333
334 assert(processor->active_thread != NULL);
335
336 pri = MAX(main_runq->highq, bound_runq->highq);
337
338 if (processor->first_timeslice) {
339 has_higher = (pri > processor->current_pri);
340 } else {
341 has_higher = (pri >= processor->current_pri);
342 }
343
344 if (has_higher) {
345 if (main_runq->urgency > 0) {
346 return AST_PREEMPT | AST_URGENT;
347 }
348
349 if (bound_runq->urgency > 0) {
350 return AST_PREEMPT | AST_URGENT;
351 }
352
353 return AST_PREEMPT;
354 }
355
356 return AST_NONE;
357 }
358
359 static boolean_t
sched_dualq_processor_queue_has_priority(processor_t processor,int priority,boolean_t gte)360 sched_dualq_processor_queue_has_priority(processor_t processor,
361 int priority,
362 boolean_t gte)
363 {
364 run_queue_t main_runq = dualq_main_runq(processor);
365 run_queue_t bound_runq = dualq_bound_runq(processor);
366
367 int qpri = MAX(main_runq->highq, bound_runq->highq);
368
369 if (gte) {
370 return qpri >= priority;
371 } else {
372 return qpri > priority;
373 }
374 }
375
376 static int
sched_dualq_runq_count(processor_t processor)377 sched_dualq_runq_count(processor_t processor)
378 {
379 return dualq_main_runq(processor)->count + dualq_bound_runq(processor)->count;
380 }
381
382 static uint64_t
sched_dualq_runq_stats_count_sum(processor_t processor)383 sched_dualq_runq_stats_count_sum(processor_t processor)
384 {
385 uint64_t bound_sum = dualq_bound_runq(processor)->runq_stats.count_sum;
386
387 if (processor->cpu_id == processor->processor_set->cpu_set_low) {
388 return bound_sum + dualq_main_runq(processor)->runq_stats.count_sum;
389 } else {
390 return bound_sum;
391 }
392 }
393 static int
sched_dualq_processor_bound_count(processor_t processor)394 sched_dualq_processor_bound_count(processor_t processor)
395 {
396 return dualq_bound_runq(processor)->count;
397 }
398
399 static void
sched_dualq_processor_queue_shutdown(processor_t processor)400 sched_dualq_processor_queue_shutdown(processor_t processor)
401 {
402 processor_set_t pset = processor->processor_set;
403 run_queue_t rq = dualq_main_runq(processor);
404 thread_t thread;
405 queue_head_t tqueue;
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 pset_unlock(pset);
410 return;
411 }
412
413 queue_init(&tqueue);
414
415 while (rq->count > 0) {
416 thread = run_queue_dequeue(rq, SCHED_HEADQ);
417 enqueue_tail(&tqueue, &thread->runq_links);
418 }
419
420 pset_unlock(pset);
421
422 qe_foreach_element_safe(thread, &tqueue, runq_links) {
423 remqueue(&thread->runq_links);
424
425 thread_lock(thread);
426
427 thread_setrun(thread, SCHED_TAILQ);
428
429 thread_unlock(thread);
430 }
431 }
432
433 static boolean_t
sched_dualq_processor_queue_remove(processor_t processor,thread_t thread)434 sched_dualq_processor_queue_remove(
435 processor_t processor,
436 thread_t thread)
437 {
438 run_queue_t rq;
439 processor_set_t pset = processor->processor_set;
440
441 pset_lock(pset);
442
443 rq = dualq_runq_for_thread(processor, thread);
444
445 if (processor == thread_get_runq_locked(thread)) {
446 /*
447 * Thread is on a run queue and we have a lock on
448 * that run queue.
449 */
450 run_queue_remove(rq, thread);
451 } else {
452 /*
453 * The thread left the run queue before we could
454 * lock the run queue.
455 */
456 thread_assert_runq_null(thread);
457 processor = PROCESSOR_NULL;
458 }
459
460 pset_unlock(pset);
461
462 return processor != PROCESSOR_NULL;
463 }
464
465 static thread_t
sched_dualq_steal_thread(processor_set_t pset)466 sched_dualq_steal_thread(processor_set_t pset)
467 {
468 processor_set_t cset = pset;
469 processor_set_t nset = next_pset(cset);
470 thread_t thread;
471
472 #if CONFIG_SCHED_SMT
473 /* Secondary processors on SMT systems never steal */
474 assert(current_processor()->processor_primary == current_processor());
475 #endif /* CONFIG_SCHED_SMT */
476
477 while (nset != pset) {
478 pset_unlock(cset);
479 cset = nset;
480 pset_lock(cset);
481
482 if (pset_has_stealable_threads(cset)) {
483 /* Need task_restrict logic here */
484 thread = run_queue_dequeue(&cset->pset_runq, SCHED_HEADQ);
485 pset_unlock(cset);
486 return thread;
487 }
488
489 nset = next_pset(cset);
490 }
491
492 pset_unlock(cset);
493
494 return THREAD_NULL;
495 }
496
497 static void
sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context)498 sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context)
499 {
500 boolean_t restart_needed = FALSE;
501 processor_t processor = processor_list;
502 processor_set_t pset;
503 thread_t thread;
504 spl_t s;
505
506 /*
507 * We update the threads associated with each processor (bound and idle threads)
508 * and then update the threads in each pset runqueue.
509 */
510
511 do {
512 do {
513 pset = processor->processor_set;
514
515 s = splsched();
516 pset_lock(pset);
517
518 restart_needed = runq_scan(dualq_bound_runq(processor), scan_context);
519
520 pset_unlock(pset);
521 splx(s);
522
523 if (restart_needed) {
524 break;
525 }
526
527 thread = processor->idle_thread;
528 if (thread != THREAD_NULL && thread->sched_stamp != os_atomic_load(&sched_tick, relaxed)) {
529 if (thread_update_add_thread(thread) == FALSE) {
530 restart_needed = TRUE;
531 break;
532 }
533 }
534 } while ((processor = processor->processor_list) != NULL);
535
536 /* Ok, we now have a collection of candidates -- fix them. */
537 thread_update_process_threads();
538 } while (restart_needed);
539
540 pset = &pset0;
541
542 do {
543 do {
544 s = splsched();
545 pset_lock(pset);
546
547 restart_needed = runq_scan(&pset->pset_runq, scan_context);
548
549 pset_unlock(pset);
550 splx(s);
551
552 if (restart_needed) {
553 break;
554 }
555 } while ((pset = pset->pset_list) != NULL);
556
557 /* Ok, we now have a collection of candidates -- fix them. */
558 thread_update_process_threads();
559 } while (restart_needed);
560 }
561
562 extern int sched_allow_rt_smt;
563
564 /* Return true if this thread should not continue running on this processor */
565 static bool
sched_dualq_thread_avoid_processor(processor_t processor,thread_t thread,__unused ast_t reason)566 sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread, __unused ast_t reason)
567 {
568 if (thread->bound_processor == processor) {
569 /* Thread is bound here */
570 return false;
571 }
572
573 #if CONFIG_SCHED_SMT
574 if (processor->processor_primary != processor) {
575 /*
576 * This is a secondary SMT processor. If the primary is running
577 * a realtime thread, only allow realtime threads on the secondary.
578 */
579 processor_t primary = processor->processor_primary;
580 if ((primary->current_pri >= BASEPRI_RTQUEUES) && ((thread->sched_pri < BASEPRI_RTQUEUES) || !sched_allow_rt_smt)) {
581 return true;
582 }
583
584 /* NO_SMT threads are not allowed on secondary processors */
585 if (thread_no_smt(thread)) {
586 return true;
587 }
588
589 if (primary->state == PROCESSOR_RUNNING) {
590 if (processor_active_thread_no_smt(primary)) {
591 /* No threads allowed on secondary if primary has NO_SMT */
592 return true;
593 }
594 }
595 }
596
597 if (processor->processor_secondary != PROCESSOR_NULL) {
598 /*
599 * This is a primary SMT processor. If the secondary is running
600 * a bound thread, the primary may not run a NO_SMT thread.
601 */
602 processor_t secondary = processor->processor_secondary;
603
604 if (secondary->state == PROCESSOR_RUNNING) {
605 if (secondary->current_is_bound && thread_no_smt(thread)) {
606 return true;
607 }
608 }
609 }
610 #endif /* CONFIG_SCHED_SMT */
611
612 return false;
613 }
614