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,
60 sched_options_t options);
61
62 static boolean_t
63 sched_dualq_processor_queue_remove(processor_t processor, thread_t thread);
64
65 static ast_t
66 sched_dualq_processor_csw_check(processor_t processor);
67
68 static boolean_t
69 sched_dualq_processor_queue_has_priority(processor_t processor, int priority, boolean_t gte);
70
71 static int
72 sched_dualq_runq_count(processor_t processor);
73
74 static boolean_t
75 sched_dualq_processor_queue_empty(processor_t processor);
76
77 static uint64_t
78 sched_dualq_runq_stats_count_sum(processor_t processor);
79
80 static int
81 sched_dualq_processor_bound_count(processor_t processor);
82
83 static void
84 sched_dualq_pset_init(processor_set_t pset);
85
86 static void
87 sched_dualq_processor_init(processor_t processor);
88
89 static thread_t
90 sched_dualq_choose_thread(processor_t processor, int priority, ast_t reason);
91
92 static void
93 sched_dualq_processor_queue_shutdown(processor_t processor);
94
95 static sched_mode_t
96 sched_dualq_initial_thread_sched_mode(task_t parent_task);
97
98 static bool
99 sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread);
100
101 const 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))
157 static inline run_queue_t
dualq_main_runq(processor_t processor)158 dualq_main_runq(processor_t processor)
159 {
160 return &processor->processor_set->pset_runq;
161 }
162
163 __attribute__((always_inline))
164 static inline run_queue_t
dualq_bound_runq(processor_t processor)165 dualq_bound_runq(processor_t processor)
166 {
167 return &processor->runq;
168 }
169
170 __attribute__((always_inline))
171 static inline run_queue_t
dualq_runq_for_thread(processor_t processor,thread_t thread)172 dualq_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
182 static sched_mode_t
sched_dualq_initial_thread_sched_mode(task_t parent_task)183 sched_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
192 static void
sched_dualq_processor_init(processor_t processor)193 sched_dualq_processor_init(processor_t processor)
194 {
195 run_queue_init(&processor->runq);
196 }
197
198 static void
sched_dualq_pset_init(processor_set_t pset)199 sched_dualq_pset_init(processor_set_t pset)
200 {
201 run_queue_init(&pset->pset_runq);
202 }
203
204 extern int sched_allow_NO_SMT_threads;
205 static void
sched_dualq_init(void)206 sched_dualq_init(void)
207 {
208 sched_timeshare_init();
209
210 if (PE_parse_boot_argn("disable_NO_SMT_threads", NULL, 0)) {
211 sched_allow_NO_SMT_threads = 0;
212 }
213 }
214
215 static thread_t
sched_dualq_choose_thread(processor_t processor,int priority,__unused ast_t reason)216 sched_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(chosen_runq, SCHED_HEADQ);
246 }
247
248 if (processor->is_SMT) {
249 thread_t potential_thread = run_queue_peek(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(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(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(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(chosen_runq, SCHED_HEADQ);
285 }
286
287 static boolean_t
sched_dualq_processor_enqueue(processor_t processor,thread_t thread,sched_options_t options)288 sched_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(rq, thread, options);
297 thread->runq = processor;
298
299 return result;
300 }
301
302 static boolean_t
sched_dualq_processor_queue_empty(processor_t processor)303 sched_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
309 static ast_t
sched_dualq_processor_csw_check(processor_t processor)310 sched_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, current_thread())) {
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
347 static boolean_t
sched_dualq_processor_queue_has_priority(processor_t processor,int priority,boolean_t gte)348 sched_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
364 static int
sched_dualq_runq_count(processor_t processor)365 sched_dualq_runq_count(processor_t processor)
366 {
367 return dualq_main_runq(processor)->count + dualq_bound_runq(processor)->count;
368 }
369
370 static uint64_t
sched_dualq_runq_stats_count_sum(processor_t processor)371 sched_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 }
381 static int
sched_dualq_processor_bound_count(processor_t processor)382 sched_dualq_processor_bound_count(processor_t processor)
383 {
384 return dualq_bound_runq(processor)->count;
385 }
386
387 static void
sched_dualq_processor_queue_shutdown(processor_t processor)388 sched_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(rq, SCHED_HEADQ);
405 enqueue_tail(&tqueue, &thread->runq_links);
406 }
407
408 pset_unlock(pset);
409
410 qe_foreach_element_safe(thread, &tqueue, runq_links) {
411 remqueue(&thread->runq_links);
412
413 thread_lock(thread);
414
415 thread_setrun(thread, SCHED_TAILQ);
416
417 thread_unlock(thread);
418 }
419 }
420
421 static boolean_t
sched_dualq_processor_queue_remove(processor_t processor,thread_t thread)422 sched_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->runq) {
434 /*
435 * Thread is on a run queue and we have a lock on
436 * that run queue.
437 */
438 run_queue_remove(rq, thread);
439 } else {
440 /*
441 * The thread left the run queue before we could
442 * lock the run queue.
443 */
444 assert(thread->runq == PROCESSOR_NULL);
445 processor = PROCESSOR_NULL;
446 }
447
448 pset_unlock(pset);
449
450 return processor != PROCESSOR_NULL;
451 }
452
453 static thread_t
sched_dualq_steal_thread(processor_set_t pset)454 sched_dualq_steal_thread(processor_set_t pset)
455 {
456 processor_set_t cset = pset;
457 processor_set_t nset = next_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(cset)) {
469 /* Need task_restrict logic here */
470 thread = run_queue_dequeue(&cset->pset_runq, SCHED_HEADQ);
471 pset_unlock(cset);
472 return thread;
473 }
474
475 nset = next_pset(cset);
476 }
477
478 pset_unlock(cset);
479
480 return THREAD_NULL;
481 }
482
483 static void
sched_dualq_thread_update_scan(sched_update_scan_context_t scan_context)484 sched_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(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(&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
548 extern int sched_allow_rt_smt;
549
550 /* Return true if this thread should not continue running on this processor */
551 static bool
sched_dualq_thread_avoid_processor(processor_t processor,thread_t thread)552 sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread)
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(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