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, integer_t options); |
60 | |
61 | static boolean_t |
62 | sched_dualq_processor_queue_remove(processor_t processor, thread_t thread); |
63 | |
64 | static ast_t |
65 | sched_dualq_processor_csw_check(processor_t processor); |
66 | |
67 | static boolean_t |
68 | sched_dualq_processor_queue_has_priority(processor_t processor, int priority, boolean_t gte); |
69 | |
70 | static int |
71 | sched_dualq_runq_count(processor_t processor); |
72 | |
73 | static boolean_t |
74 | sched_dualq_processor_queue_empty(processor_t processor); |
75 | |
76 | static uint64_t |
77 | sched_dualq_runq_stats_count_sum(processor_t processor); |
78 | |
79 | static int |
80 | sched_dualq_processor_bound_count(processor_t processor); |
81 | |
82 | static void |
83 | sched_dualq_pset_init(processor_set_t pset); |
84 | |
85 | static void |
86 | sched_dualq_processor_init(processor_t processor); |
87 | |
88 | static thread_t |
89 | sched_dualq_choose_thread(processor_t processor, int priority, ast_t reason); |
90 | |
91 | static void |
92 | sched_dualq_processor_queue_shutdown(processor_t processor); |
93 | |
94 | static sched_mode_t |
95 | sched_dualq_initial_thread_sched_mode(task_t parent_task); |
96 | |
97 | static bool |
98 | sched_dualq_thread_avoid_processor(processor_t processor, thread_t thread); |
99 | |
100 | const 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)) |
149 | static inline run_queue_t dualq_main_runq(processor_t processor) |
150 | { |
151 | return &processor->processor_set->pset_runq; |
152 | } |
153 | |
154 | __attribute__((always_inline)) |
155 | static inline run_queue_t dualq_bound_runq(processor_t processor) |
156 | { |
157 | return &processor->runq; |
158 | } |
159 | |
160 | __attribute__((always_inline)) |
161 | static 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 | |
171 | static sched_mode_t |
172 | sched_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 | |
180 | static void |
181 | sched_dualq_processor_init(processor_t processor) |
182 | { |
183 | run_queue_init(&processor->runq); |
184 | } |
185 | |
186 | static void |
187 | sched_dualq_pset_init(processor_set_t pset) |
188 | { |
189 | run_queue_init(&pset->pset_runq); |
190 | } |
191 | |
192 | static void |
193 | sched_dualq_init(void) |
194 | { |
195 | sched_timeshare_init(); |
196 | } |
197 | |
198 | static thread_t |
199 | sched_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 | |
229 | static boolean_t |
230 | sched_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 | |
244 | static boolean_t |
245 | sched_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 | |
251 | static ast_t |
252 | sched_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 | |
287 | static boolean_t |
288 | sched_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 | |
303 | static int |
304 | sched_dualq_runq_count(processor_t processor) |
305 | { |
306 | return dualq_main_runq(processor)->count + dualq_bound_runq(processor)->count; |
307 | } |
308 | |
309 | static uint64_t |
310 | sched_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 | } |
319 | static int |
320 | sched_dualq_processor_bound_count(processor_t processor) |
321 | { |
322 | return dualq_bound_runq(processor)->count; |
323 | } |
324 | |
325 | static void |
326 | sched_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 | |
360 | static boolean_t |
361 | sched_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 | |
393 | static thread_t |
394 | sched_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 | |
421 | static void |
422 | sched_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 | |
486 | extern int sched_allow_rt_smt; |
487 | |
488 | /* Return true if this thread should not continue running on this processor */ |
489 | static bool |
490 | sched_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 | |