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