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, __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 | .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 |
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 |
165 | dualq_bound_runq(processor_t processor) |
166 | { |
167 | return &processor->runq; |
168 | } |
169 | |
170 | __attribute__((always_inline)) |
171 | static inline run_queue_t |
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 |
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 |
193 | sched_dualq_processor_init(processor_t processor) |
194 | { |
195 | run_queue_init(runq: &processor->runq); |
196 | } |
197 | |
198 | static void |
199 | sched_dualq_pset_init(processor_set_t pset) |
200 | { |
201 | run_queue_init(runq: &pset->pset_runq); |
202 | } |
203 | |
204 | extern int sched_allow_NO_SMT_threads; |
205 | static void |
206 | sched_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 | |
215 | static thread_t |
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(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 | |
287 | static boolean_t |
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(runq: rq, thread, options); |
297 | thread_set_runq_locked(thread, new_runq: processor); |
298 | |
299 | return result; |
300 | } |
301 | |
302 | static boolean_t |
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 |
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, 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 | |
347 | static boolean_t |
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 |
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 |
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 |
382 | sched_dualq_processor_bound_count(processor_t processor) |
383 | { |
384 | return dualq_bound_runq(processor)->count; |
385 | } |
386 | |
387 | static void |
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(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 | |
421 | static boolean_t |
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_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 | |
453 | static thread_t |
454 | sched_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 | |
483 | static void |
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(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 | |
548 | extern int sched_allow_rt_smt; |
549 | |
550 | /* Return true if this thread should not continue running on this processor */ |
551 | static bool |
552 | sched_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 | |