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