1 /* $NetBSD: kern_runq.c,v 1.71 2025/01/17 04:11:33 mrg Exp $ */
2
3 /*-
4 * Copyright (c) 2019, 2020 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Andrew Doran.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /*
33 * Copyright (c) 2007, 2008 Mindaugas Rasiukevicius <rmind at NetBSD org>
34 * All rights reserved.
35 *
36 * Redistribution and use in source and binary forms, with or without
37 * modification, are permitted provided that the following conditions
38 * are met:
39 * 1. Redistributions of source code must retain the above copyright
40 * notice, this list of conditions and the following disclaimer.
41 * 2. Redistributions in binary form must reproduce the above copyright
42 * notice, this list of conditions and the following disclaimer in the
43 * documentation and/or other materials provided with the distribution.
44 *
45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
46 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
47 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
48 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
49 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
50 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
51 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
52 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
53 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
54 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
55 * SUCH DAMAGE.
56 */
57
58 #include <sys/cdefs.h>
59 __KERNEL_RCSID(0, "$NetBSD: kern_runq.c,v 1.71 2025/01/17 04:11:33 mrg Exp $");
60
61 #include "opt_dtrace.h"
62
63 #include <sys/param.h>
64 #include <sys/kernel.h>
65 #include <sys/bitops.h>
66 #include <sys/cpu.h>
67 #include <sys/idle.h>
68 #include <sys/intr.h>
69 #include <sys/kmem.h>
70 #include <sys/lwp.h>
71 #include <sys/mutex.h>
72 #include <sys/proc.h>
73 #include <sys/pset.h>
74 #include <sys/sched.h>
75 #include <sys/syscallargs.h>
76 #include <sys/sysctl.h>
77 #include <sys/systm.h>
78 #include <sys/types.h>
79 #include <sys/evcnt.h>
80 #include <sys/atomic.h>
81
82 /*
83 * Bits per map.
84 */
85 #define BITMAP_BITS (32)
86 #define BITMAP_SHIFT (5)
87 #define BITMAP_MSB (0x80000000U)
88 #define BITMAP_MASK (BITMAP_BITS - 1)
89
90 const int schedppq = 1;
91
92 static void *sched_getrq(struct schedstate_percpu *, const pri_t);
93 #ifdef MULTIPROCESSOR
94 static lwp_t * sched_catchlwp(struct cpu_info *);
95 #endif
96
97 /*
98 * Preemption control.
99 */
100 #ifdef __HAVE_PREEMPTION
101 # ifdef DEBUG
102 int sched_kpreempt_pri = 0;
103 # else
104 int sched_kpreempt_pri = PRI_USER_RT;
105 # endif
106 #else
107 int sched_kpreempt_pri = 1000;
108 #endif
109
110 /*
111 * Migration and balancing.
112 */
113 static u_int cacheht_time; /* Cache hotness time */
114 static u_int min_catch; /* Minimal LWP count for catching */
115 static u_int skim_interval; /* Rate limit for stealing LWPs */
116
117 #ifdef KDTRACE_HOOKS
118 struct lwp *curthread;
119 #endif
120
121 void
runq_init(void)122 runq_init(void)
123 {
124
125 /* Pulling from remote packages, LWP must not have run for 10ms. */
126 cacheht_time = 10;
127
128 /* Minimal count of LWPs for catching */
129 min_catch = 1;
130
131 /* Steal from other CPUs at most every 10ms. */
132 skim_interval = 10;
133 }
134
135 void
sched_cpuattach(struct cpu_info * ci)136 sched_cpuattach(struct cpu_info *ci)
137 {
138 struct schedstate_percpu *spc;
139 size_t size;
140 void *p;
141 u_int i;
142
143 spc = &ci->ci_schedstate;
144 spc->spc_nextpkg = ci;
145
146 if (spc->spc_lwplock == NULL) {
147 spc->spc_lwplock = mutex_obj_alloc(MUTEX_DEFAULT, IPL_SCHED);
148 }
149 if (ci == lwp0.l_cpu) {
150 /* Initialize the scheduler structure of the primary LWP */
151 lwp0.l_mutex = spc->spc_lwplock;
152 }
153 if (spc->spc_mutex != NULL) {
154 /* Already initialized. */
155 return;
156 }
157
158 /* Allocate the run queue */
159 size = roundup2(sizeof(spc->spc_queue[0]) * PRI_COUNT, coherency_unit) +
160 coherency_unit;
161 p = kmem_alloc(size, KM_SLEEP);
162 spc->spc_queue = (void *)roundup2((uintptr_t)p, coherency_unit);
163
164 /* Initialize run queues */
165 spc->spc_mutex = mutex_obj_alloc(MUTEX_DEFAULT, IPL_SCHED);
166 for (i = 0; i < PRI_COUNT; i++)
167 TAILQ_INIT(&spc->spc_queue[i]);
168 }
169
170 /*
171 * Control of the runqueue.
172 */
173 static inline void *
sched_getrq(struct schedstate_percpu * spc,const pri_t prio)174 sched_getrq(struct schedstate_percpu *spc, const pri_t prio)
175 {
176
177 KASSERT(prio < PRI_COUNT);
178 return &spc->spc_queue[prio];
179 }
180
181 /*
182 * Put an LWP onto a run queue. The LWP must be locked by spc_mutex for
183 * l_cpu.
184 */
185 void
sched_enqueue(struct lwp * l)186 sched_enqueue(struct lwp *l)
187 {
188 struct schedstate_percpu *spc;
189 TAILQ_HEAD(, lwp) *q_head;
190 const pri_t eprio = lwp_eprio(l);
191 struct cpu_info *ci;
192
193 ci = l->l_cpu;
194 spc = &ci->ci_schedstate;
195 KASSERT(lwp_locked(l, l->l_cpu->ci_schedstate.spc_mutex));
196
197 /* Enqueue the thread */
198 q_head = sched_getrq(spc, eprio);
199 if (TAILQ_EMPTY(q_head)) {
200 u_int i;
201 uint32_t q;
202
203 /* Mark bit */
204 i = eprio >> BITMAP_SHIFT;
205 q = BITMAP_MSB >> (eprio & BITMAP_MASK);
206 KASSERT((spc->spc_bitmap[i] & q) == 0);
207 spc->spc_bitmap[i] |= q;
208 }
209
210 /*
211 * Determine run queue position according to POSIX. XXX Explicitly
212 * lowering a thread's priority with pthread_setschedparam() is not
213 * handled.
214 */
215 if ((l->l_pflag & LP_PREEMPTING) != 0) {
216 switch (l->l_class) {
217 case SCHED_OTHER:
218 TAILQ_INSERT_TAIL(q_head, l, l_runq);
219 break;
220 case SCHED_FIFO:
221 TAILQ_INSERT_HEAD(q_head, l, l_runq);
222 break;
223 case SCHED_RR:
224 if (getticks() - l->l_rticks >= sched_rrticks) {
225 TAILQ_INSERT_TAIL(q_head, l, l_runq);
226 } else {
227 TAILQ_INSERT_HEAD(q_head, l, l_runq);
228 }
229 break;
230 default:
231 panic("sched_enqueue: LWP %p has class %d\n",
232 l, l->l_class);
233 }
234 } else {
235 TAILQ_INSERT_TAIL(q_head, l, l_runq);
236 }
237 spc->spc_flags &= ~SPCF_IDLE;
238 spc->spc_count++;
239 if ((l->l_pflag & LP_BOUND) == 0) {
240 atomic_store_relaxed(&spc->spc_mcount,
241 atomic_load_relaxed(&spc->spc_mcount) + 1);
242 }
243
244 /*
245 * Update the value of highest priority in the runqueue,
246 * if priority of this thread is higher.
247 */
248 if (eprio > spc->spc_maxpriority)
249 spc->spc_maxpriority = eprio;
250
251 sched_newts(l);
252 }
253
254 /*
255 * Remove and LWP from the run queue it's on. The LWP must be in state
256 * LSRUN.
257 */
258 void
sched_dequeue(struct lwp * l)259 sched_dequeue(struct lwp *l)
260 {
261 TAILQ_HEAD(, lwp) *q_head;
262 struct schedstate_percpu *spc;
263 const pri_t eprio = lwp_eprio(l);
264
265 spc = &l->l_cpu->ci_schedstate;
266
267 KASSERT(lwp_locked(l, spc->spc_mutex));
268 KASSERT(eprio <= spc->spc_maxpriority);
269 KASSERT(spc->spc_bitmap[eprio >> BITMAP_SHIFT] != 0);
270 KASSERT(spc->spc_count > 0);
271
272 if (spc->spc_migrating == l)
273 spc->spc_migrating = NULL;
274
275 spc->spc_count--;
276 if ((l->l_pflag & LP_BOUND) == 0) {
277 atomic_store_relaxed(&spc->spc_mcount,
278 atomic_load_relaxed(&spc->spc_mcount) - 1);
279 }
280
281 q_head = sched_getrq(spc, eprio);
282 TAILQ_REMOVE(q_head, l, l_runq);
283 if (TAILQ_EMPTY(q_head)) {
284 u_int i;
285 uint32_t q;
286
287 /* Unmark bit */
288 i = eprio >> BITMAP_SHIFT;
289 q = BITMAP_MSB >> (eprio & BITMAP_MASK);
290 KASSERT((spc->spc_bitmap[i] & q) != 0);
291 spc->spc_bitmap[i] &= ~q;
292
293 /*
294 * Update the value of highest priority in the runqueue, in a
295 * case it was a last thread in the queue of highest priority.
296 */
297 if (eprio != spc->spc_maxpriority)
298 return;
299
300 do {
301 if (spc->spc_bitmap[i] != 0) {
302 q = ffs(spc->spc_bitmap[i]);
303 spc->spc_maxpriority =
304 (i << BITMAP_SHIFT) + (BITMAP_BITS - q);
305 return;
306 }
307 } while (i--);
308
309 /* If not found - set the lowest value */
310 spc->spc_maxpriority = 0;
311 }
312 }
313
314 /*
315 * Cause a preemption on the given CPU, if the priority "pri" is higher
316 * priority than the running LWP. If "unlock" is specified, and ideally it
317 * will be for concurrency reasons, spc_mutex will be dropped before return.
318 */
319 void
sched_resched_cpu(struct cpu_info * ci,pri_t pri,bool unlock)320 sched_resched_cpu(struct cpu_info *ci, pri_t pri, bool unlock)
321 {
322 struct schedstate_percpu *spc;
323 u_int o, n, f;
324 lwp_t *l;
325
326 spc = &ci->ci_schedstate;
327
328 KASSERT(mutex_owned(spc->spc_mutex));
329
330 /*
331 * If the priority level we're evaluating wouldn't cause a new LWP
332 * to be run on the CPU, then we have nothing to do.
333 */
334 if (pri <= spc->spc_curpriority || !mp_online) {
335 if (__predict_true(unlock)) {
336 spc_unlock(ci);
337 }
338 return;
339 }
340
341 /*
342 * Figure out what kind of preemption we should do.
343 */
344 l = ci->ci_onproc;
345 if ((l->l_flag & LW_IDLE) != 0) {
346 f = RESCHED_IDLE | RESCHED_UPREEMPT;
347 } else if (pri >= sched_kpreempt_pri && (l->l_pflag & LP_INTR) == 0) {
348 /* We can't currently preempt softints - should be able to. */
349 #ifdef __HAVE_PREEMPTION
350 f = RESCHED_KPREEMPT;
351 #else
352 /* Leave door open for test: set kpreempt_pri with sysctl. */
353 f = RESCHED_UPREEMPT;
354 #endif
355 /*
356 * l_dopreempt must be set with the CPU locked to sync with
357 * mi_switch(). It must also be set with an atomic to sync
358 * with kpreempt().
359 */
360 atomic_or_uint(&l->l_dopreempt, DOPREEMPT_ACTIVE);
361 } else {
362 f = RESCHED_UPREEMPT;
363 }
364 if (ci != curcpu()) {
365 f |= RESCHED_REMOTE;
366 }
367
368 /*
369 * Things can start as soon as ci_want_resched is touched: x86 has
370 * an instruction that monitors the memory cell it's in. Drop the
371 * schedstate lock in advance, otherwise the remote CPU can awaken
372 * and immediately block on the lock.
373 */
374 if (__predict_true(unlock)) {
375 spc_unlock(ci);
376 }
377
378 /*
379 * The caller almost always has a second scheduler lock held: either
380 * the running LWP lock (spc_lwplock), or a sleep queue lock. That
381 * keeps preemption disabled, which among other things ensures all
382 * LWPs involved won't be freed while we're here (see lwp_dtor()).
383 */
384 KASSERT(kpreempt_disabled());
385
386 for (o = 0;; o = n) {
387 n = atomic_cas_uint(&ci->ci_want_resched, o, o | f);
388 if (__predict_true(o == n)) {
389 /*
390 * We're the first to set a resched on the CPU. Try
391 * to avoid causing a needless trip through trap()
392 * to handle an AST fault, if it's known the LWP
393 * will either block or go through userret() soon.
394 */
395 if (l != curlwp || cpu_intr_p()) {
396 cpu_need_resched(ci, l, f);
397 }
398 break;
399 }
400 if (__predict_true(
401 (n & (RESCHED_KPREEMPT|RESCHED_UPREEMPT)) >=
402 (f & (RESCHED_KPREEMPT|RESCHED_UPREEMPT)))) {
403 /* Already in progress, nothing to do. */
404 break;
405 }
406 }
407 }
408
409 /*
410 * Cause a preemption on the given CPU, if the priority of LWP "l" in state
411 * LSRUN, is higher priority than the running LWP. If "unlock" is
412 * specified, and ideally it will be for concurrency reasons, spc_mutex will
413 * be dropped before return.
414 */
415 void
sched_resched_lwp(struct lwp * l,bool unlock)416 sched_resched_lwp(struct lwp *l, bool unlock)
417 {
418 struct cpu_info *ci = l->l_cpu;
419
420 KASSERT(lwp_locked(l, ci->ci_schedstate.spc_mutex));
421 KASSERT(l->l_stat == LSRUN);
422
423 sched_resched_cpu(ci, lwp_eprio(l), unlock);
424 }
425
426 /*
427 * Migration and balancing.
428 */
429
430 #ifdef MULTIPROCESSOR
431
432 /*
433 * Estimate if LWP is cache-hot.
434 */
435 static inline bool
lwp_cache_hot(const struct lwp * l)436 lwp_cache_hot(const struct lwp *l)
437 {
438
439 /* Leave new LWPs in peace, determination has already been made. */
440 if (l->l_stat == LSIDL)
441 return true;
442
443 if (__predict_false(l->l_slptime != 0 || l->l_rticks == 0))
444 return false;
445
446 return (getticks() - l->l_rticks < mstohz(cacheht_time));
447 }
448
449 /*
450 * Check if LWP can migrate to the chosen CPU.
451 */
452 static inline bool
sched_migratable(const struct lwp * l,struct cpu_info * ci)453 sched_migratable(const struct lwp *l, struct cpu_info *ci)
454 {
455 const struct schedstate_percpu *spc = &ci->ci_schedstate;
456 KASSERT(lwp_locked(__UNCONST(l), NULL));
457
458 /* Is CPU offline? */
459 if (__predict_false(spc->spc_flags & SPCF_OFFLINE))
460 return false;
461
462 /* Is affinity set? */
463 if (__predict_false(l->l_affinity))
464 return kcpuset_isset(l->l_affinity, cpu_index(ci));
465
466 /* Is there a processor-set? */
467 return (spc->spc_psid == l->l_psid);
468 }
469
470 /*
471 * A small helper to do round robin through CPU packages.
472 */
473 static struct cpu_info *
sched_nextpkg(void)474 sched_nextpkg(void)
475 {
476 struct schedstate_percpu *spc = &curcpu()->ci_schedstate;
477
478 spc->spc_nextpkg =
479 spc->spc_nextpkg->ci_sibling[CPUREL_PACKAGE1ST];
480
481 return spc->spc_nextpkg;
482 }
483
484 /*
485 * Find a CPU to run LWP "l". Look for the CPU with the lowest priority
486 * thread. In case of equal priority, prefer first class CPUs, and amongst
487 * the remainder choose the CPU with the fewest runqueue entries.
488 *
489 * Begin the search in the CPU package which "pivot" is a member of.
490 */
491 static struct cpu_info * __noinline
sched_bestcpu(struct lwp * l,struct cpu_info * pivot)492 sched_bestcpu(struct lwp *l, struct cpu_info *pivot)
493 {
494 struct cpu_info *bestci, *curci, *outer;
495 struct schedstate_percpu *bestspc, *curspc;
496 pri_t bestpri, curpri;
497
498 /*
499 * If this fails (it shouldn't), run on the given CPU. This also
500 * gives us a weak preference for "pivot" to begin with.
501 */
502 bestci = pivot;
503 bestspc = &bestci->ci_schedstate;
504 if (sched_migratable(l, bestci)) {
505 bestpri = MAX(bestspc->spc_curpriority,
506 bestspc->spc_maxpriority);
507 } else {
508 /* Invalidate the priority. */
509 bestpri = PRI_COUNT;
510 }
511
512 /* In the outer loop scroll through all CPU packages. */
513 pivot = pivot->ci_package1st;
514 outer = pivot;
515 do {
516 /* In the inner loop scroll through all CPUs in package. */
517 curci = outer;
518 do {
519 if (!sched_migratable(l, curci)) {
520 continue;
521 }
522
523 curspc = &curci->ci_schedstate;
524
525 /* If this CPU is idle and 1st class, we're done. */
526 if (cpu_is_idle_1stclass(curci)) {
527 return curci;
528 }
529
530 curpri = MAX(curspc->spc_curpriority,
531 curspc->spc_maxpriority);
532
533 if (curpri > bestpri) {
534 continue;
535 }
536 if (curpri == bestpri) {
537 /* Prefer first class CPUs over others. */
538 if (cpu_is_better(bestci, curci)) {
539 continue;
540 }
541 /*
542 * Pick the least busy CPU. Make sure this is not
543 * <=, otherwise it defeats the above preference.
544 */
545 if (bestspc->spc_count < curspc->spc_count) {
546 continue;
547 }
548 }
549
550 bestpri = curpri;
551 bestci = curci;
552 bestspc = curspc;
553
554 } while (curci = curci->ci_sibling[CPUREL_PACKAGE],
555 curci != outer);
556 } while (outer = outer->ci_sibling[CPUREL_PACKAGE1ST],
557 outer != pivot);
558
559 return bestci;
560 }
561
562 /*
563 * Estimate the migration of LWP to the other CPU.
564 * Take and return the CPU, if migration is needed.
565 */
566 struct cpu_info *
sched_takecpu(struct lwp * l)567 sched_takecpu(struct lwp *l)
568 {
569 struct schedstate_percpu *spc;
570 struct cpu_info *ci, *curci, *tci;
571 pri_t eprio;
572 int flags;
573
574 KASSERT(lwp_locked(l, NULL));
575
576 /* If thread is strictly bound, do not estimate other CPUs */
577 ci = l->l_cpu;
578 if (l->l_pflag & LP_BOUND)
579 return ci;
580
581 spc = &ci->ci_schedstate;
582 eprio = lwp_eprio(l);
583
584 /*
585 * Handle new LWPs. For vfork() with a timeshared child, make it
586 * run on the same CPU as the parent if no other LWPs in queue.
587 * Otherwise scatter far and wide - try for an even distribution
588 * across all CPU packages and CPUs.
589 */
590 if (l->l_stat == LSIDL) {
591 if (curlwp->l_vforkwaiting && l->l_class == SCHED_OTHER) {
592 if (sched_migratable(l, curlwp->l_cpu) && eprio >
593 curlwp->l_cpu->ci_schedstate.spc_maxpriority) {
594 return curlwp->l_cpu;
595 }
596 } else {
597 return sched_bestcpu(l, sched_nextpkg());
598 }
599 flags = SPCF_IDLE;
600 } else {
601 flags = SPCF_IDLE | SPCF_1STCLASS;
602 }
603
604 /*
605 * Try to send the LWP back to the first CPU in the same core if
606 * idle. This keeps LWPs clustered in the run queues of 1st class
607 * CPUs. This implies stickiness. If we didn't find a home for
608 * a vfork() child above, try to use any SMT sibling to help out.
609 */
610 tci = ci;
611 do {
612 if (cpu_is_type(tci, flags) && sched_migratable(l, tci)) {
613 return tci;
614 }
615 tci = tci->ci_sibling[CPUREL_CORE];
616 } while (tci != ci);
617
618 /*
619 * Otherwise the LWP is "sticky", i.e. generally preferring to stay
620 * on the same CPU.
621 */
622 if (sched_migratable(l, ci) && (eprio > spc->spc_curpriority ||
623 (lwp_cache_hot(l) && l->l_class == SCHED_OTHER))) {
624 return ci;
625 }
626
627 /*
628 * If the current CPU core is idle, run there and avoid the
629 * expensive scan of CPUs below.
630 */
631 curci = curcpu();
632 tci = curci;
633 do {
634 if (cpu_is_type(tci, flags) && sched_migratable(l, tci)) {
635 return tci;
636 }
637 tci = tci->ci_sibling[CPUREL_CORE];
638 } while (tci != curci);
639
640 /*
641 * Didn't find a new home above - happens infrequently. Start the
642 * search in last CPU package that the LWP ran in, but expand to
643 * include the whole system if needed.
644 */
645 return sched_bestcpu(l, l->l_cpu);
646 }
647
648 /*
649 * Tries to catch an LWP from the runqueue of other CPU.
650 */
651 static struct lwp *
sched_catchlwp(struct cpu_info * ci)652 sched_catchlwp(struct cpu_info *ci)
653 {
654 struct cpu_info *curci = curcpu();
655 struct schedstate_percpu *spc, *curspc;
656 TAILQ_HEAD(, lwp) *q_head;
657 struct lwp *l;
658 bool gentle;
659
660 curspc = &curci->ci_schedstate;
661 spc = &ci->ci_schedstate;
662
663 /*
664 * Be more aggressive if this CPU is first class, and the other
665 * is not.
666 */
667 gentle = cpu_is_better(curci, ci);
668
669 if (atomic_load_relaxed(&spc->spc_mcount) < (gentle ? min_catch : 1) ||
670 curspc->spc_psid != spc->spc_psid) {
671 spc_unlock(ci);
672 return NULL;
673 }
674
675 /* Take the highest priority thread */
676 q_head = sched_getrq(spc, spc->spc_maxpriority);
677 l = TAILQ_FIRST(q_head);
678
679 for (;;) {
680 /* Check the first and next result from the queue */
681 if (l == NULL) {
682 break;
683 }
684 KASSERTMSG(l->l_stat == LSRUN, "%s l %p (%s) l_stat %d",
685 ci->ci_data.cpu_name,
686 l, (l->l_name ? l->l_name : l->l_proc->p_comm), l->l_stat);
687
688 /* Look for threads, whose are allowed to migrate */
689 if ((l->l_pflag & LP_BOUND) ||
690 (gentle && lwp_cache_hot(l)) ||
691 !sched_migratable(l, curci)) {
692 l = TAILQ_NEXT(l, l_runq);
693 /* XXX Gap: could walk down priority list. */
694 continue;
695 }
696
697 /* Grab the thread, and move to the local run queue */
698 sched_dequeue(l);
699 l->l_cpu = curci;
700 lwp_unlock_to(l, curspc->spc_mutex);
701 sched_enqueue(l);
702 return l;
703 }
704 spc_unlock(ci);
705
706 return l;
707 }
708
709 /*
710 * Called from sched_idle() to handle migration. Return the CPU that we
711 * pushed the LWP to (may be NULL).
712 */
713 static struct cpu_info *
sched_idle_migrate(void)714 sched_idle_migrate(void)
715 {
716 struct cpu_info *ci = curcpu(), *tci = NULL;
717 struct schedstate_percpu *spc, *tspc;
718 bool dlock = false;
719
720 spc = &ci->ci_schedstate;
721 spc_lock(ci);
722 for (;;) {
723 struct lwp *l;
724
725 l = spc->spc_migrating;
726 if (l == NULL)
727 break;
728
729 /*
730 * If second attempt, and target CPU has changed,
731 * drop the old lock.
732 */
733 if (dlock == true && tci != l->l_target_cpu) {
734 KASSERT(tci != NULL);
735 spc_unlock(tci);
736 dlock = false;
737 }
738
739 /*
740 * Nothing to do if destination has changed to the
741 * local CPU, or migration was done by other CPU.
742 */
743 tci = l->l_target_cpu;
744 if (tci == NULL || tci == ci) {
745 spc->spc_migrating = NULL;
746 l->l_target_cpu = NULL;
747 break;
748 }
749 tspc = &tci->ci_schedstate;
750
751 /*
752 * Double-lock the runqueues.
753 * We do that only once.
754 */
755 if (dlock == false) {
756 dlock = true;
757 if (ci < tci) {
758 spc_lock(tci);
759 } else if (!mutex_tryenter(tspc->spc_mutex)) {
760 spc_unlock(ci);
761 spc_lock(tci);
762 spc_lock(ci);
763 /* Check the situation again.. */
764 continue;
765 }
766 }
767
768 /* Migrate the thread */
769 KASSERT(l->l_stat == LSRUN);
770 spc->spc_migrating = NULL;
771 l->l_target_cpu = NULL;
772 sched_dequeue(l);
773 l->l_cpu = tci;
774 lwp_setlock(l, tspc->spc_mutex);
775 sched_enqueue(l);
776 sched_resched_lwp(l, true);
777 /* tci now unlocked */
778 spc_unlock(ci);
779 return tci;
780 }
781 if (dlock == true) {
782 KASSERT(tci != NULL);
783 spc_unlock(tci);
784 }
785 spc_unlock(ci);
786 return NULL;
787 }
788
789 /*
790 * Try to steal an LWP from "tci".
791 */
792 static bool
sched_steal(struct cpu_info * ci,struct cpu_info * tci)793 sched_steal(struct cpu_info *ci, struct cpu_info *tci)
794 {
795 struct schedstate_percpu *spc, *tspc;
796 lwp_t *l;
797
798 spc = &ci->ci_schedstate;
799 tspc = &tci->ci_schedstate;
800 if (atomic_load_relaxed(&tspc->spc_mcount) != 0 &&
801 spc->spc_psid == tspc->spc_psid) {
802 spc_dlock(ci, tci);
803 l = sched_catchlwp(tci);
804 spc_unlock(ci);
805 if (l != NULL) {
806 return true;
807 }
808 }
809 return false;
810 }
811
812 /*
813 * Called from each CPU's idle loop.
814 */
815 void
sched_idle(void)816 sched_idle(void)
817 {
818 struct cpu_info *ci, *inner, *outer, *first, *tci, *mci;
819 struct schedstate_percpu *spc, *tspc;
820 struct lwp *l;
821
822 ci = curcpu();
823 spc = &ci->ci_schedstate;
824 tci = NULL;
825 mci = NULL;
826
827 /*
828 * Handle LWP migrations off this CPU to another. If there a is
829 * migration to do then remember the CPU the LWP was sent to, and
830 * don't steal the LWP back from that CPU below.
831 */
832 if (spc->spc_migrating != NULL) {
833 mci = sched_idle_migrate();
834 }
835
836 /* If this CPU is offline, or we have an LWP to run, we're done. */
837 if ((spc->spc_flags & SPCF_OFFLINE) != 0 || spc->spc_count != 0) {
838 return;
839 }
840
841 /* Deal with SMT. */
842 if (ci->ci_nsibling[CPUREL_CORE] > 1) {
843 /* Try to help our siblings out. */
844 tci = ci->ci_sibling[CPUREL_CORE];
845 while (tci != ci) {
846 if (tci != mci && sched_steal(ci, tci)) {
847 return;
848 }
849 tci = tci->ci_sibling[CPUREL_CORE];
850 }
851 /*
852 * If not the first SMT in the core, and in the default
853 * processor set, the search ends here.
854 */
855 if ((spc->spc_flags & SPCF_1STCLASS) == 0 &&
856 spc->spc_psid == PS_NONE) {
857 return;
858 }
859 }
860
861 /*
862 * Find something to run, unless this CPU exceeded the rate limit.
863 * Start looking on the current package to maximise L2/L3 cache
864 * locality. Then expand to looking at the rest of the system.
865 *
866 * XXX Should probably look at 2nd class CPUs first, but they will
867 * shed jobs via preempt() anyway.
868 */
869 if (spc->spc_nextskim > getticks()) {
870 return;
871 }
872 spc->spc_nextskim = getticks() + mstohz(skim_interval);
873
874 /* In the outer loop scroll through all CPU packages, starting here. */
875 first = ci->ci_package1st;
876 outer = first;
877 do {
878 /* In the inner loop scroll through all CPUs in package. */
879 inner = outer;
880 do {
881 /* Don't hit the locks unless needed. */
882 tspc = &inner->ci_schedstate;
883 if (ci == inner || ci == mci ||
884 spc->spc_psid != tspc->spc_psid ||
885 atomic_load_relaxed(&tspc->spc_mcount) < min_catch) {
886 continue;
887 }
888 spc_dlock(ci, inner);
889 l = sched_catchlwp(inner);
890 spc_unlock(ci);
891 if (l != NULL) {
892 /* Got it! */
893 return;
894 }
895 } while (inner = inner->ci_sibling[CPUREL_PACKAGE],
896 inner != outer);
897 } while (outer = outer->ci_sibling[CPUREL_PACKAGE1ST],
898 outer != first);
899 }
900
901 /*
902 * Called from mi_switch() when an LWP has been preempted / has yielded.
903 * The LWP is presently in the CPU's run queue. Here we look for a better
904 * CPU to teleport the LWP to; there may not be one.
905 */
906 void
sched_preempted(struct lwp * l)907 sched_preempted(struct lwp *l)
908 {
909 struct schedstate_percpu *tspc;
910 struct cpu_info *ci, *tci;
911
912 ci = l->l_cpu;
913 tspc = &ci->ci_schedstate;
914
915 KASSERT(tspc->spc_count >= 1);
916
917 /*
918 * Try to select another CPU if:
919 *
920 * - there is no migration pending already
921 * - and this LWP is running on a 2nd class CPU
922 * - or this LWP is a child of vfork() that has just done execve()
923 */
924 if (l->l_target_cpu != NULL ||
925 (cpu_is_1stclass(ci) &&
926 (l->l_pflag & LP_TELEPORT) == 0)) {
927 return;
928 }
929
930 /*
931 * Fast path: if the first SMT in the core is idle, send it back
932 * there, because the cache is shared (cheap) and we want all LWPs
933 * to be clustered on 1st class CPUs (either running there or on
934 * their runqueues).
935 */
936 tci = ci->ci_sibling[CPUREL_CORE];
937 while (tci != ci) {
938 tspc = &tci->ci_schedstate;
939 if (cpu_is_idle_1stclass(tci) && sched_migratable(l, tci)) {
940 l->l_target_cpu = tci;
941 l->l_pflag &= ~LP_TELEPORT;
942 return;
943 }
944 tci = tci->ci_sibling[CPUREL_CORE];
945 }
946
947 if ((l->l_pflag & LP_TELEPORT) != 0) {
948 /*
949 * A child of vfork(): now that the parent is released,
950 * scatter far and wide, to match the LSIDL distribution
951 * done in sched_takecpu().
952 */
953 l->l_pflag &= ~LP_TELEPORT;
954 tci = sched_bestcpu(l, sched_nextpkg());
955 if (tci != ci) {
956 l->l_target_cpu = tci;
957 }
958 } else {
959 /*
960 * Try to find a better CPU to take it, but don't move to
961 * another 2nd class CPU, and don't move to a non-idle CPU,
962 * because that would prevent SMT being used to maximise
963 * throughput.
964 *
965 * Search in the current CPU package in order to try and
966 * keep L2/L3 cache locality, but expand to include the
967 * whole system if needed.
968 */
969 tci = sched_bestcpu(l, l->l_cpu);
970 if (tci != ci && cpu_is_idle_1stclass(tci)) {
971 l->l_target_cpu = tci;
972 }
973 }
974 }
975
976 /*
977 * Called during execve() by a child of vfork(). Does two things:
978 *
979 * - If the parent has been awoken and put back on curcpu then give the
980 * CPU back to the parent.
981 *
982 * - If curlwp is not on a 1st class CPU then find somewhere else to run,
983 * since it dodged the distribution in sched_takecpu() when first set
984 * runnable.
985 */
986 void
sched_vforkexec(struct lwp * l,bool samecpu)987 sched_vforkexec(struct lwp *l, bool samecpu)
988 {
989
990 KASSERT(l == curlwp);
991 if ((samecpu && ncpu > 1) || !cpu_is_1stclass(l->l_cpu)) {
992 l->l_pflag |= LP_TELEPORT;
993 preempt();
994 }
995 }
996
997 #else
998
999 /*
1000 * stubs for !MULTIPROCESSOR
1001 */
1002
1003 struct cpu_info *
sched_takecpu(struct lwp * l)1004 sched_takecpu(struct lwp *l)
1005 {
1006
1007 return l->l_cpu;
1008 }
1009
1010 void
sched_idle(void)1011 sched_idle(void)
1012 {
1013
1014 }
1015
1016 void
sched_preempted(struct lwp * l)1017 sched_preempted(struct lwp *l)
1018 {
1019
1020 }
1021
1022 void
sched_vforkexec(struct lwp * l,bool samecpu)1023 sched_vforkexec(struct lwp *l, bool samecpu)
1024 {
1025
1026 KASSERT(l == curlwp);
1027 }
1028
1029 #endif /* MULTIPROCESSOR */
1030
1031 /*
1032 * Scheduling statistics and balancing.
1033 */
1034 void
sched_lwp_stats(struct lwp * l)1035 sched_lwp_stats(struct lwp *l)
1036 {
1037 int batch;
1038
1039 KASSERT(lwp_locked(l, NULL));
1040
1041 /* Update sleep time */
1042 if (l->l_stat == LSSLEEP || l->l_stat == LSSTOP ||
1043 l->l_stat == LSSUSPENDED)
1044 l->l_slptime++;
1045
1046 /*
1047 * Set that thread is more CPU-bound, if sum of run time exceeds the
1048 * sum of sleep time. Check if thread is CPU-bound a first time.
1049 */
1050 batch = (l->l_rticksum > l->l_slpticksum);
1051 if (batch != 0) {
1052 if ((l->l_flag & LW_BATCH) == 0)
1053 batch = 0;
1054 l->l_flag |= LW_BATCH;
1055 } else
1056 l->l_flag &= ~LW_BATCH;
1057
1058 /* Reset the time sums */
1059 l->l_slpticksum = 0;
1060 l->l_rticksum = 0;
1061
1062 /* Scheduler-specific hook */
1063 sched_pstats_hook(l, batch);
1064 #ifdef KDTRACE_HOOKS
1065 curthread = l;
1066 #endif
1067 }
1068
1069 /*
1070 * Scheduler mill.
1071 */
1072 struct lwp *
sched_nextlwp(void)1073 sched_nextlwp(void)
1074 {
1075 struct cpu_info *ci = curcpu();
1076 struct schedstate_percpu *spc;
1077 TAILQ_HEAD(, lwp) *q_head;
1078 struct lwp *l;
1079
1080 /* Update the last run time on switch */
1081 l = curlwp;
1082 l->l_rticksum += (getticks() - l->l_rticks);
1083
1084 /* Return to idle LWP if there is a migrating thread */
1085 spc = &ci->ci_schedstate;
1086 if (__predict_false(spc->spc_migrating != NULL))
1087 return NULL;
1088
1089 /* Return to idle LWP if there is no runnable job */
1090 if (__predict_false(spc->spc_count == 0))
1091 return NULL;
1092
1093 /* Take the highest priority thread */
1094 KASSERT(spc->spc_bitmap[spc->spc_maxpriority >> BITMAP_SHIFT]);
1095 q_head = sched_getrq(spc, spc->spc_maxpriority);
1096 l = TAILQ_FIRST(q_head);
1097 KASSERT(l != NULL);
1098
1099 sched_oncpu(l);
1100 l->l_rticks = getticks();
1101
1102 return l;
1103 }
1104
1105 /*
1106 * sched_curcpu_runnable_p: return if curcpu() should exit the idle loop.
1107 */
1108
1109 bool
sched_curcpu_runnable_p(void)1110 sched_curcpu_runnable_p(void)
1111 {
1112 const struct cpu_info *ci;
1113 const struct schedstate_percpu *spc;
1114 bool rv;
1115
1116 kpreempt_disable();
1117 ci = curcpu();
1118 spc = &ci->ci_schedstate;
1119 rv = (spc->spc_count != 0);
1120 #ifndef __HAVE_FAST_SOFTINTS
1121 rv |= (ci->ci_data.cpu_softints != 0);
1122 #endif
1123 kpreempt_enable();
1124
1125 return rv;
1126 }
1127
1128 /*
1129 * Sysctl nodes and initialization.
1130 */
1131
1132 SYSCTL_SETUP(sysctl_sched_setup, "sysctl sched setup")
1133 {
1134 const struct sysctlnode *node = NULL;
1135
1136 sysctl_createv(clog, 0, NULL, &node,
1137 CTLFLAG_PERMANENT,
1138 CTLTYPE_NODE, "sched",
1139 SYSCTL_DESCR("Scheduler options"),
1140 NULL, 0, NULL, 0,
1141 CTL_KERN, CTL_CREATE, CTL_EOL);
1142
1143 if (node == NULL)
1144 return;
1145
1146 sysctl_createv(clog, 0, &node, NULL,
1147 CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
1148 CTLTYPE_INT, "cacheht_time",
1149 SYSCTL_DESCR("Cache hotness time (in ms)"),
1150 NULL, 0, &cacheht_time, 0,
1151 CTL_CREATE, CTL_EOL);
1152 sysctl_createv(clog, 0, &node, NULL,
1153 CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
1154 CTLTYPE_INT, "skim_interval",
1155 SYSCTL_DESCR("Rate limit for stealing from other CPUs (in ms)"),
1156 NULL, 0, &skim_interval, 0,
1157 CTL_CREATE, CTL_EOL);
1158 sysctl_createv(clog, 0, &node, NULL,
1159 CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
1160 CTLTYPE_INT, "min_catch",
1161 SYSCTL_DESCR("Minimal count of threads for catching"),
1162 NULL, 0, &min_catch, 0,
1163 CTL_CREATE, CTL_EOL);
1164 sysctl_createv(clog, 0, &node, NULL,
1165 CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
1166 CTLTYPE_INT, "timesoftints",
1167 SYSCTL_DESCR("Track CPU time for soft interrupts"),
1168 NULL, 0, &softint_timing, 0,
1169 CTL_CREATE, CTL_EOL);
1170 sysctl_createv(clog, 0, &node, NULL,
1171 CTLFLAG_PERMANENT | CTLFLAG_READWRITE,
1172 CTLTYPE_INT, "kpreempt_pri",
1173 SYSCTL_DESCR("Minimum priority to trigger kernel preemption"),
1174 NULL, 0, &sched_kpreempt_pri, 0,
1175 CTL_CREATE, CTL_EOL);
1176 }
1177
1178 /*
1179 * Debugging.
1180 */
1181
1182 #ifdef DDB
1183
1184 void
sched_print_runqueue(void (* pr)(const char *,...))1185 sched_print_runqueue(void (*pr)(const char *, ...))
1186 {
1187 struct cpu_info *ci, *tci;
1188 struct schedstate_percpu *spc;
1189 struct lwp *l;
1190 struct proc *p;
1191 CPU_INFO_ITERATOR cii;
1192
1193 for (CPU_INFO_FOREACH(cii, ci)) {
1194 int i;
1195
1196 spc = &ci->ci_schedstate;
1197
1198 (*pr)("Run-queue (CPU = %u):\n", ci->ci_index);
1199 (*pr)(" pid.lid = %d.%d, r_count = %u, "
1200 "maxpri = %d, mlwp = %p\n",
1201 #ifdef MULTIPROCESSOR
1202 ci->ci_curlwp->l_proc->p_pid, ci->ci_curlwp->l_lid,
1203 #else
1204 curlwp->l_proc->p_pid, curlwp->l_lid,
1205 #endif
1206 spc->spc_count, spc->spc_maxpriority,
1207 spc->spc_migrating);
1208 i = (PRI_COUNT >> BITMAP_SHIFT) - 1;
1209 do {
1210 uint32_t q;
1211 q = spc->spc_bitmap[i];
1212 (*pr)(" bitmap[%d] => [ %d (0x%x) ]\n", i, ffs(q), q);
1213 } while (i--);
1214 }
1215
1216 (*pr)(" %5s %4s %4s %10s %3s %18s %4s %4s %s\n",
1217 "LID", "PRI", "EPRI", "FL", "ST", "LWP", "CPU", "TCI", "LRTICKS");
1218
1219 PROCLIST_FOREACH(p, &allproc) {
1220 (*pr)(" /- %d (%s)\n", (int)p->p_pid, p->p_comm);
1221 LIST_FOREACH(l, &p->p_lwps, l_sibling) {
1222 ci = l->l_cpu;
1223 tci = l->l_target_cpu;
1224 (*pr)(" | %5d %4u %4u 0x%8.8x %3s %18p %4u %4d %u\n",
1225 (int)l->l_lid, l->l_priority, lwp_eprio(l),
1226 l->l_flag, l->l_stat == LSRUN ? "RQ" :
1227 (l->l_stat == LSSLEEP ? "SQ" : "-"),
1228 l, ci->ci_index, (tci ? tci->ci_index : -1),
1229 (u_int)(getticks() - l->l_rticks));
1230 }
1231 }
1232 }
1233
1234 #endif
1235