1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1982, 1986, 1990, 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 * (c) UNIX System Laboratories, Inc.
7 * All or some portions of this file are derived from material licensed
8 * to the University of California by American Telephone and Telegraph
9 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
10 * the permission of UNIX System Laboratories, Inc.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37 #include "opt_hwpmc_hooks.h"
38 #include "opt_hwt_hooks.h"
39 #include "opt_sched.h"
40
41 #include <sys/systm.h>
42 #include <sys/cpuset.h>
43 #include <sys/kernel.h>
44 #include <sys/ktr.h>
45 #include <sys/lock.h>
46 #include <sys/kthread.h>
47 #include <sys/mutex.h>
48 #include <sys/proc.h>
49 #include <sys/resourcevar.h>
50 #include <sys/runq.h>
51 #include <sys/sched.h>
52 #include <sys/sdt.h>
53 #include <sys/smp.h>
54 #include <sys/sysctl.h>
55 #include <sys/sx.h>
56 #include <sys/turnstile.h>
57 #include <sys/umtxvar.h>
58 #include <machine/pcb.h>
59 #include <machine/smp.h>
60
61 #ifdef HWPMC_HOOKS
62 #include <sys/pmckern.h>
63 #endif
64
65 #ifdef HWT_HOOKS
66 #include <dev/hwt/hwt_hook.h>
67 #endif
68
69 /*
70 * INVERSE_ESTCPU_WEIGHT is only suitable for statclock() frequencies in
71 * the range 100-256 Hz (approximately).
72 */
73 #define INVERSE_ESTCPU_WEIGHT 8 /* 1 / (priorities per estcpu level). */
74 #define NICE_WEIGHT 1 /* Priorities per nice level. */
75 _Static_assert(NICE_WEIGHT * (PRIO_MAX - PRIO_MIN)
76 <= PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE,
77 "Priority range accounting for nice values cannot exceed the including "
78 "timeshare span.");
79 #define ESTCPULIM(e) \
80 min((e), INVERSE_ESTCPU_WEIGHT * \
81 (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE - \
82 (PRIO_MAX - PRIO_MIN) * NICE_WEIGHT) \
83 + INVERSE_ESTCPU_WEIGHT - 1)
84
85 #define TS_NAME_LEN (MAXCOMLEN + sizeof(" td ") + sizeof(__XSTRING(UINT_MAX)))
86
87 /*
88 * The schedulable entity that runs a context.
89 * This is an extension to the thread structure and is tailored to
90 * the requirements of this scheduler.
91 * All fields are protected by the scheduler lock.
92 */
93 struct td_sched {
94 fixpt_t ts_pctcpu; /* %cpu during p_swtime. */
95 u_int ts_estcpu; /* Estimated cpu utilization. */
96 int ts_cpticks; /* Ticks of cpu time. */
97 int ts_slptime; /* Seconds !RUNNING. */
98 int ts_slice; /* Remaining part of time slice. */
99 int ts_flags;
100 int ts_rqcpu; /* That CPU's runq or NOCPU => global */
101 #ifdef KTR
102 char ts_name[TS_NAME_LEN];
103 #endif
104 };
105
106 /* flags kept in td_flags */
107 #define TDF_DIDRUN TDF_SCHED0 /* thread actually ran. */
108 #define TDF_BOUND TDF_SCHED1 /* Bound to one CPU. */
109 #define TDF_SLICEEND TDF_SCHED2 /* Thread time slice is over. */
110
111 #define TDP_RESCHED TDP_SCHED1 /* Reschedule due to maybe_resched(). */
112
113 /* flags kept in ts_flags */
114 #define TSF_AFFINITY 0x0001 /* Has a non-"full" CPU set. */
115
116 #ifdef SMP
117 #define TS_RUNQ_PTR(ts) ((ts)->ts_rqcpu == NOCPU ? \
118 (&runq_global) : (DPCPU_ID_PTR((ts)->ts_rqcpu, runq_pcpu)))
119 #else
120 #define TS_RUNQ_PTR(ts) (&runq_global)
121 #endif
122
123 #define THREAD_CAN_SCHED(td, cpu) \
124 CPU_ISSET((cpu), &(td)->td_cpuset->cs_mask)
125
126 _Static_assert(sizeof(struct thread) + sizeof(struct td_sched) <=
127 sizeof(struct thread0_storage),
128 "increase struct thread0_storage.t0st_sched size");
129
130 static struct mtx sched_lock;
131
132 static int realstathz = 127; /* stathz is sometimes 0 and run off of hz. */
133 static int sched_tdcnt; /* Total runnable threads in the system. */
134 static int sched_slice = 12; /* Thread run time before rescheduling. */
135
136 static inline void
sched_update_hogticks(void)137 sched_update_hogticks(void)
138 {
139 hogticks = imax(1, (2 * hz * sched_slice + realstathz / 2) /
140 realstathz);
141 }
142
143 static void setup_runqs(void);
144 static void schedcpu(void);
145 static void schedcpu_thread(void);
146 static void sched_priority(struct thread *td, u_char prio);
147 static void maybe_resched(struct thread *td);
148 static void updatepri(struct thread *td);
149 static void resetpriority(struct thread *td);
150 static void resetpriority_thread(struct thread *td);
151 #ifdef SMP
152 static int sched_pickcpu(struct thread *td);
153 static int forward_wakeup(int cpunum);
154 static void kick_other_cpu(int pri, int cpuid);
155 #endif
156
157 static struct kproc_desc sched_kp = {
158 "schedcpu",
159 schedcpu_thread,
160 NULL
161 };
162
163 static void
sched_4bsd_sysinit(void)164 sched_4bsd_sysinit(void)
165 {
166 kproc_start(&sched_kp);
167 }
168
169 /*
170 * Global run queue.
171 */
172 static struct runq runq_global;
173
174 #ifdef SMP
175 /*
176 * Per-CPU run queues
177 */
178 DPCPU_DEFINE_STATIC(struct runq, runq_pcpu);
179 DPCPU_DEFINE_STATIC(long, runq_length);
180
181 static cpuset_t idle_cpus_mask;
182 #endif
183
184 struct pcpuidlestat {
185 u_int idlecalls;
186 u_int oldidlecalls;
187 };
188 DPCPU_DEFINE_STATIC(struct pcpuidlestat, idlestat);
189
190 static void
setup_runqs(void)191 setup_runqs(void)
192 {
193 #ifdef SMP
194 int cpu;
195
196 CPU_FOREACH(cpu)
197 runq_init(DPCPU_ID_PTR(cpu, runq_pcpu));
198 #endif
199
200 runq_init(&runq_global);
201 }
202
203 static int
sysctl_kern_4bsd_quantum(SYSCTL_HANDLER_ARGS)204 sysctl_kern_4bsd_quantum(SYSCTL_HANDLER_ARGS)
205 {
206 int error, new_val, period;
207
208 period = 1000000 / realstathz;
209 new_val = period * sched_slice;
210 error = sysctl_handle_int(oidp, &new_val, 0, req);
211 if (error != 0 || req->newptr == NULL)
212 return (error);
213 if (new_val <= 0)
214 return (EINVAL);
215 sched_slice = imax(1, (new_val + period / 2) / period);
216 sched_update_hogticks();
217 return (0);
218 }
219
220 static int
sysctl_kern_slice(SYSCTL_HANDLER_ARGS)221 sysctl_kern_slice(SYSCTL_HANDLER_ARGS)
222 {
223 int error, new_val;
224
225 new_val = sched_slice;
226 error = sysctl_handle_int(oidp, &new_val, 0, req);
227 if (error != 0 || req->newptr == NULL)
228 return (error);
229 if (new_val <= 0)
230 return (EINVAL);
231 sched_slice = new_val;
232 sched_update_hogticks();
233 return (0);
234 }
235
236 SYSCTL_NODE(_kern_sched, OID_AUTO, 4bsd, CTLFLAG_RD | CTLFLAG_MPSAFE, 0,
237 "4BSD Scheduler");
238
239 SYSCTL_PROC(_kern_sched_4bsd, OID_AUTO, quantum,
240 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
241 sysctl_kern_4bsd_quantum, "I",
242 "Quantum for timeshare threads in microseconds");
243 SYSCTL_PROC(_kern_sched_4bsd, OID_AUTO, slice,
244 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
245 sysctl_kern_slice, "I",
246 "Quantum for timeshare threads in stathz ticks");
247 #ifdef SMP
248 /* Enable forwarding of wakeups to all other cpus */
249 static SYSCTL_NODE(_kern_sched_4bsd, OID_AUTO, ipiwakeup,
250 CTLFLAG_RD | CTLFLAG_MPSAFE, NULL,
251 "Kernel SMP");
252
253 static int runq_fuzz = 1;
254 SYSCTL_INT(_kern_sched_4bsd, OID_AUTO, runq_fuzz, CTLFLAG_RW,
255 &runq_fuzz, 0, "");
256
257 static int forward_wakeup_enabled = 1;
258 SYSCTL_INT(_kern_sched_4bsd_ipiwakeup, OID_AUTO, enabled, CTLFLAG_RW,
259 &forward_wakeup_enabled, 0,
260 "Forwarding of wakeup to idle CPUs");
261
262 static int forward_wakeups_requested = 0;
263 SYSCTL_INT(_kern_sched_4bsd_ipiwakeup, OID_AUTO, requested, CTLFLAG_RD,
264 &forward_wakeups_requested, 0,
265 "Requests for Forwarding of wakeup to idle CPUs");
266
267 static int forward_wakeups_delivered = 0;
268 SYSCTL_INT(_kern_sched_4bsd_ipiwakeup, OID_AUTO, delivered, CTLFLAG_RD,
269 &forward_wakeups_delivered, 0,
270 "Completed Forwarding of wakeup to idle CPUs");
271
272 static int forward_wakeup_use_mask = 1;
273 SYSCTL_INT(_kern_sched_4bsd_ipiwakeup, OID_AUTO, usemask, CTLFLAG_RW,
274 &forward_wakeup_use_mask, 0,
275 "Use the mask of idle cpus");
276
277 static int forward_wakeup_use_loop = 0;
278 SYSCTL_INT(_kern_sched_4bsd_ipiwakeup, OID_AUTO, useloop, CTLFLAG_RW,
279 &forward_wakeup_use_loop, 0,
280 "Use a loop to find idle cpus");
281
282 #endif
283
284 static __inline void
sched_load_add(void)285 sched_load_add(void)
286 {
287
288 sched_tdcnt++;
289 KTR_COUNTER0(KTR_SCHED, "load", "global load", sched_tdcnt);
290 SDT_PROBE2(sched, , , load__change, NOCPU, sched_tdcnt);
291 }
292
293 static __inline void
sched_load_rem(void)294 sched_load_rem(void)
295 {
296
297 sched_tdcnt--;
298 KTR_COUNTER0(KTR_SCHED, "load", "global load", sched_tdcnt);
299 SDT_PROBE2(sched, , , load__change, NOCPU, sched_tdcnt);
300 }
301
302 static void
maybe_resched_ast(struct thread * td,int tda)303 maybe_resched_ast(struct thread *td, int tda)
304 {
305 MPASS(td == curthread); /* We are AST */
306 if ((td->td_pflags & TDP_RESCHED) != 0) {
307 td->td_pflags &= ~TDP_RESCHED;
308 ast_scheduler(td, tda);
309 }
310 }
311
312 /*
313 * Arrange to reschedule if necessary, taking the priorities and
314 * schedulers into account.
315 */
316 static void
maybe_resched(struct thread * td)317 maybe_resched(struct thread *td)
318 {
319 struct thread *ctd;
320
321 ctd = curthread;
322 THREAD_LOCK_ASSERT(td, MA_OWNED);
323 if (td->td_priority < ctd->td_priority)
324 ctd->td_pflags |= TDP_RESCHED;
325 }
326
327 /*
328 * This function is called when a thread is about to be put on run queue
329 * because it has been made runnable or its priority has been adjusted. It
330 * determines if the new thread should preempt the current thread. If so,
331 * it sets td_owepreempt to request a preemption.
332 */
333 static int
maybe_preempt(struct thread * td)334 maybe_preempt(struct thread *td)
335 {
336 #ifdef PREEMPTION
337 struct thread *ctd;
338 int cpri, pri;
339
340 /*
341 * The new thread should not preempt the current thread if any of the
342 * following conditions are true:
343 *
344 * - The kernel is in the throes of crashing (panicstr).
345 * - The current thread has a higher (numerically lower) or
346 * equivalent priority. Note that this prevents curthread from
347 * trying to preempt to itself.
348 * - The current thread has an inhibitor set or is in the process of
349 * exiting. In this case, the current thread is about to switch
350 * out anyways, so there's no point in preempting. If we did,
351 * the current thread would not be properly resumed as well, so
352 * just avoid that whole landmine.
353 * - If the new thread's priority is not an interrupt priority and
354 * the current thread's priority is not an idle priority and
355 * FULL_PREEMPTION is disabled.
356 *
357 * If all of these conditions are false, but the current thread is in
358 * a nested critical section, then we have to defer the preemption
359 * until we exit the critical section. Otherwise, switch immediately
360 * to the new thread.
361 */
362 ctd = curthread;
363 THREAD_LOCK_ASSERT(td, MA_OWNED);
364 KASSERT((td->td_inhibitors == 0),
365 ("maybe_preempt: trying to run inhibited thread"));
366 pri = td->td_priority;
367 cpri = ctd->td_priority;
368 if (KERNEL_PANICKED() || pri >= cpri || TD_IS_INHIBITED(ctd))
369 return (0);
370 #ifndef FULL_PREEMPTION
371 if (pri > PRI_MAX_ITHD && cpri < PRI_MIN_IDLE)
372 return (0);
373 #endif
374
375 CTR0(KTR_PROC, "maybe_preempt: scheduling preemption");
376 ctd->td_owepreempt = 1;
377 return (1);
378 #else
379 return (0);
380 #endif
381 }
382
383 /*
384 * Constants for digital decay and forget:
385 * 90% of (ts_estcpu) usage in 5 * loadav time
386 * 95% of (ts_pctcpu) usage in 60 seconds (load insensitive)
387 * Note that, as ps(1) mentions, this can let percentages
388 * total over 100% (I've seen 137.9% for 3 processes).
389 *
390 * Note that sched_clock() updates ts_estcpu and p_cpticks asynchronously.
391 *
392 * We wish to decay away 90% of ts_estcpu in (5 * loadavg) seconds.
393 * That is, the system wants to compute a value of decay such
394 * that the following for loop:
395 * for (i = 0; i < (5 * loadavg); i++)
396 * ts_estcpu *= decay;
397 * will compute
398 * ts_estcpu *= 0.1;
399 * for all values of loadavg:
400 *
401 * Mathematically this loop can be expressed by saying:
402 * decay ** (5 * loadavg) ~= .1
403 *
404 * The system computes decay as:
405 * decay = (2 * loadavg) / (2 * loadavg + 1)
406 *
407 * We wish to prove that the system's computation of decay
408 * will always fulfill the equation:
409 * decay ** (5 * loadavg) ~= .1
410 *
411 * If we compute b as:
412 * b = 2 * loadavg
413 * then
414 * decay = b / (b + 1)
415 *
416 * We now need to prove two things:
417 * 1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
418 * 2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
419 *
420 * Facts:
421 * For x close to zero, exp(x) =~ 1 + x, since
422 * exp(x) = 0! + x**1/1! + x**2/2! + ... .
423 * therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
424 * For x close to zero, ln(1+x) =~ x, since
425 * ln(1+x) = x - x**2/2 + x**3/3 - ... -1 < x < 1
426 * therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
427 * ln(.1) =~ -2.30
428 *
429 * Proof of (1):
430 * Solve (factor)**(power) =~ .1 given power (5*loadav):
431 * solving for factor,
432 * ln(factor) =~ (-2.30/5*loadav), or
433 * factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) =
434 * exp(-1/b) =~ (b-1)/b =~ b/(b+1). QED
435 *
436 * Proof of (2):
437 * Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
438 * solving for power,
439 * power*ln(b/(b+1)) =~ -2.30, or
440 * power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav. QED
441 *
442 * Actual power values for the implemented algorithm are as follows:
443 * loadav: 1 2 3 4
444 * power: 5.68 10.32 14.94 19.55
445 */
446
447 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */
448 #define loadfactor(loadav) (2 * (loadav))
449 #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE))
450
451 extern fixpt_t ccpu;
452
453 /*
454 * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the
455 * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below
456 * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT).
457 *
458 * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used:
459 * 1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits).
460 *
461 * If you don't want to bother with the faster/more-accurate formula, you
462 * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate
463 * (more general) method of calculating the %age of CPU used by a process.
464 */
465 #define CCPU_SHIFT 11
466
467 /*
468 * Recompute process priorities, every hz ticks.
469 * MP-safe, called without the Giant mutex.
470 */
471 /* ARGSUSED */
472 static void
schedcpu(void)473 schedcpu(void)
474 {
475 fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
476 struct thread *td;
477 struct proc *p;
478 struct td_sched *ts;
479 int awake;
480
481 sx_slock(&allproc_lock);
482 FOREACH_PROC_IN_SYSTEM(p) {
483 PROC_LOCK(p);
484 if (p->p_state == PRS_NEW) {
485 PROC_UNLOCK(p);
486 continue;
487 }
488 FOREACH_THREAD_IN_PROC(p, td) {
489 awake = 0;
490 ts = td_get_sched(td);
491 thread_lock(td);
492 /*
493 * Increment sleep time (if sleeping). We
494 * ignore overflow, as above.
495 */
496 if (TD_ON_RUNQ(td)) {
497 awake = 1;
498 td->td_flags &= ~TDF_DIDRUN;
499 } else if (TD_IS_RUNNING(td)) {
500 awake = 1;
501 /* Do not clear TDF_DIDRUN */
502 } else if (td->td_flags & TDF_DIDRUN) {
503 awake = 1;
504 td->td_flags &= ~TDF_DIDRUN;
505 }
506
507 /*
508 * ts_pctcpu is only for ps and ttyinfo().
509 */
510 ts->ts_pctcpu = (ts->ts_pctcpu * ccpu) >> FSHIFT;
511 if (ts->ts_cpticks != 0) {
512 #if (FSHIFT >= CCPU_SHIFT)
513 ts->ts_pctcpu += (realstathz == 100)
514 ? ((fixpt_t) ts->ts_cpticks) <<
515 (FSHIFT - CCPU_SHIFT) :
516 100 * (((fixpt_t) ts->ts_cpticks)
517 << (FSHIFT - CCPU_SHIFT)) / realstathz;
518 #else
519 ts->ts_pctcpu += ((FSCALE - ccpu) *
520 (ts->ts_cpticks *
521 FSCALE / realstathz)) >> FSHIFT;
522 #endif
523 ts->ts_cpticks = 0;
524 }
525
526 if (awake) {
527 if (ts->ts_slptime > 1) {
528 /*
529 * In an ideal world, this should not
530 * happen, because whoever woke us
531 * up from the long sleep should have
532 * unwound the slptime and reset our
533 * priority before we run at the stale
534 * priority. Should KASSERT at some
535 * point when all the cases are fixed.
536 */
537 updatepri(td);
538 }
539 ts->ts_slptime = 0;
540 } else
541 ts->ts_slptime++;
542
543 /*
544 * If the td_sched has been idle the entire second,
545 * stop recalculating its priority until
546 * it wakes up.
547 */
548 if (ts->ts_slptime > 1) {
549 thread_unlock(td);
550 continue;
551 }
552 ts->ts_estcpu = decay_cpu(loadfac, ts->ts_estcpu);
553 resetpriority(td);
554 resetpriority_thread(td);
555 thread_unlock(td);
556 }
557 PROC_UNLOCK(p);
558 }
559 sx_sunlock(&allproc_lock);
560 }
561
562 /*
563 * Main loop for a kthread that executes schedcpu once a second.
564 */
565 static void
schedcpu_thread(void)566 schedcpu_thread(void)
567 {
568
569 for (;;) {
570 schedcpu();
571 pause("-", hz);
572 }
573 }
574
575 /*
576 * Recalculate the priority of a process after it has slept for a while.
577 * For all load averages >= 1 and max ts_estcpu of 255, sleeping for at
578 * least six times the loadfactor will decay ts_estcpu to zero.
579 */
580 static void
updatepri(struct thread * td)581 updatepri(struct thread *td)
582 {
583 struct td_sched *ts;
584 fixpt_t loadfac;
585 unsigned int newcpu;
586
587 ts = td_get_sched(td);
588 loadfac = loadfactor(averunnable.ldavg[0]);
589 if (ts->ts_slptime > 5 * loadfac)
590 ts->ts_estcpu = 0;
591 else {
592 newcpu = ts->ts_estcpu;
593 /* schedcpu() performs one decay_cpu() on its own. */
594 ts->ts_slptime--;
595 while (newcpu && --ts->ts_slptime)
596 newcpu = decay_cpu(loadfac, newcpu);
597 ts->ts_estcpu = newcpu;
598 }
599 }
600
601 /*
602 * Compute the priority of a process when running in user mode.
603 * Arrange to reschedule if the resulting priority is better
604 * than that of the current process.
605 */
606 static void
resetpriority(struct thread * td)607 resetpriority(struct thread *td)
608 {
609 u_int newpriority;
610
611 if (td->td_pri_class != PRI_TIMESHARE)
612 return;
613 newpriority = PRI_MIN_TIMESHARE +
614 td_get_sched(td)->ts_estcpu / INVERSE_ESTCPU_WEIGHT +
615 NICE_WEIGHT * (td->td_proc->p_nice - PRIO_MIN);
616 KASSERT(PRI_MIN_TIMESHARE <= newpriority &&
617 newpriority <= PRI_MAX_TIMESHARE,
618 ("Out-of-bounds priority, probably 'ts_estcpu' not clamped "
619 "correctly, see ESTCPULIM()"));
620 sched_user_prio(td, newpriority);
621 }
622
623 /*
624 * Update the thread's priority when the associated process's user
625 * priority changes.
626 */
627 static void
resetpriority_thread(struct thread * td)628 resetpriority_thread(struct thread *td)
629 {
630
631 /* Only change threads with a time sharing user priority. */
632 if (td->td_priority < PRI_MIN_TIMESHARE ||
633 td->td_priority > PRI_MAX_TIMESHARE)
634 return;
635
636 /* XXX the whole needresched thing is broken, but not silly. */
637 maybe_resched(td);
638
639 sched_prio(td, td->td_user_pri);
640 }
641
642 static void
sched_4bsd_setup(void)643 sched_4bsd_setup(void)
644 {
645 /*
646 * Decay 95% of `ts_pctcpu' in 60 seconds; see CCPU_SHIFT
647 * before changing.
648 */
649 ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
650
651 setup_runqs();
652
653 /* Account for thread0. */
654 sched_load_add();
655
656 ast_register(TDA_SCHED_PRIV, ASTR_UNCOND, 0, maybe_resched_ast);
657 }
658
659 /*
660 * This routine determines time constants after stathz and hz are setup.
661 */
662 static void
sched_4bsd_initticks(void)663 sched_4bsd_initticks(void)
664 {
665
666 realstathz = stathz ? stathz : hz;
667 sched_slice = realstathz / 10; /* ~100ms */
668 sched_update_hogticks();
669 }
670
671 /* External interfaces start here */
672
673 /*
674 * Very early in the boot some setup of scheduler-specific
675 * parts of proc0 and of some scheduler resources needs to be done.
676 * Called from:
677 * proc0_init()
678 */
679 static void
sched_4bsd_init(void)680 sched_4bsd_init(void)
681 {
682
683 /*
684 * Set up the scheduler specific parts of thread0.
685 */
686 thread0.td_lock = &sched_lock;
687 td_get_sched(&thread0)->ts_slice = sched_slice;
688 mtx_init(&sched_lock, "sched lock", NULL, MTX_SPIN);
689 }
690
691 static void
sched_4bsd_init_ap(void)692 sched_4bsd_init_ap(void)
693 {
694
695 /* Nothing needed. */
696 }
697
698 static bool
sched_4bsd_runnable(void)699 sched_4bsd_runnable(void)
700 {
701 #ifdef SMP
702 return (runq_not_empty(&runq_global) ||
703 runq_not_empty(DPCPU_PTR(runq_pcpu)));
704 #else
705 return (runq_not_empty(&runq_global));
706 #endif
707 }
708
709 static int
sched_4bsd_rr_interval(void)710 sched_4bsd_rr_interval(void)
711 {
712
713 /* Convert sched_slice from stathz to hz. */
714 return (imax(1, (sched_slice * hz + realstathz / 2) / realstathz));
715 }
716
717 /*
718 * We adjust the priority of the current process. The priority of a
719 * process gets worse as it accumulates CPU time. The cpu usage
720 * estimator (ts_estcpu) is increased here. resetpriority() will
721 * compute a different priority each time ts_estcpu increases by
722 * INVERSE_ESTCPU_WEIGHT (until PRI_MAX_TIMESHARE is reached). The
723 * cpu usage estimator ramps up quite quickly when the process is
724 * running (linearly), and decays away exponentially, at a rate which
725 * is proportionally slower when the system is busy. The basic
726 * principle is that the system will 90% forget that the process used
727 * a lot of CPU time in 5 * loadav seconds. This causes the system to
728 * favor processes which haven't run much recently, and to round-robin
729 * among other processes.
730 */
731 static void
sched_clock_tick(struct thread * td)732 sched_clock_tick(struct thread *td)
733 {
734 struct pcpuidlestat *stat;
735 struct td_sched *ts;
736
737 THREAD_LOCK_ASSERT(td, MA_OWNED);
738 ts = td_get_sched(td);
739
740 ts->ts_cpticks++;
741 ts->ts_estcpu = ESTCPULIM(ts->ts_estcpu + 1);
742 if ((ts->ts_estcpu % INVERSE_ESTCPU_WEIGHT) == 0) {
743 resetpriority(td);
744 resetpriority_thread(td);
745 }
746
747 /*
748 * Force a context switch if the current thread has used up a full
749 * time slice (default is 100ms).
750 */
751 if (!TD_IS_IDLETHREAD(td) && --ts->ts_slice <= 0) {
752 ts->ts_slice = sched_slice;
753
754 /*
755 * If an ithread uses a full quantum, demote its
756 * priority and preempt it.
757 */
758 if (PRI_BASE(td->td_pri_class) == PRI_ITHD) {
759 SCHED_STAT_INC(ithread_preemptions);
760 td->td_owepreempt = 1;
761 if (td->td_base_pri + RQ_PPQ < PRI_MAX_ITHD) {
762 SCHED_STAT_INC(ithread_demotions);
763 sched_prio(td, td->td_base_pri + RQ_PPQ);
764 }
765 } else {
766 td->td_flags |= TDF_SLICEEND;
767 ast_sched_locked(td, TDA_SCHED);
768 }
769 }
770
771 stat = DPCPU_PTR(idlestat);
772 stat->oldidlecalls = stat->idlecalls;
773 stat->idlecalls = 0;
774 }
775
776 static void
sched_4bsd_clock(struct thread * td,int cnt)777 sched_4bsd_clock(struct thread *td, int cnt)
778 {
779
780 for ( ; cnt > 0; cnt--)
781 sched_clock_tick(td);
782 }
783
784 /*
785 * Charge child's scheduling CPU usage to parent.
786 */
787 static void
sched_4bsd_exit(struct proc * p,struct thread * td)788 sched_4bsd_exit(struct proc *p, struct thread *td)
789 {
790
791 KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "proc exit",
792 "prio:%d", td->td_priority);
793
794 PROC_LOCK_ASSERT(p, MA_OWNED);
795 sched_exit_thread(FIRST_THREAD_IN_PROC(p), td);
796 }
797
798 static void
sched_4bsd_exit_thread(struct thread * td,struct thread * child)799 sched_4bsd_exit_thread(struct thread *td, struct thread *child)
800 {
801
802 KTR_STATE1(KTR_SCHED, "thread", sched_tdname(child), "exit",
803 "prio:%d", child->td_priority);
804 thread_lock(td);
805 td_get_sched(td)->ts_estcpu = ESTCPULIM(td_get_sched(td)->ts_estcpu +
806 td_get_sched(child)->ts_estcpu);
807 thread_unlock(td);
808 thread_lock(child);
809 if ((child->td_flags & TDF_NOLOAD) == 0)
810 sched_load_rem();
811 thread_unlock(child);
812 }
813
814 static void
sched_4bsd_fork(struct thread * td,struct thread * childtd)815 sched_4bsd_fork(struct thread *td, struct thread *childtd)
816 {
817 sched_fork_thread(td, childtd);
818 }
819
820 static void
sched_4bsd_fork_thread(struct thread * td,struct thread * childtd)821 sched_4bsd_fork_thread(struct thread *td, struct thread *childtd)
822 {
823 struct td_sched *ts, *tsc;
824
825 childtd->td_oncpu = NOCPU;
826 childtd->td_lastcpu = NOCPU;
827 childtd->td_lock = &sched_lock;
828 childtd->td_cpuset = cpuset_ref(td->td_cpuset);
829 childtd->td_domain.dr_policy = td->td_cpuset->cs_domain;
830 childtd->td_priority = childtd->td_base_pri;
831 ts = td_get_sched(childtd);
832 bzero(ts, sizeof(*ts));
833 tsc = td_get_sched(td);
834 ts->ts_estcpu = tsc->ts_estcpu;
835 ts->ts_flags |= (tsc->ts_flags & TSF_AFFINITY);
836 ts->ts_slice = 1;
837 }
838
839 static void
sched_4bsd_nice(struct proc * p,int nice)840 sched_4bsd_nice(struct proc *p, int nice)
841 {
842 struct thread *td;
843
844 PROC_LOCK_ASSERT(p, MA_OWNED);
845 p->p_nice = nice;
846 FOREACH_THREAD_IN_PROC(p, td) {
847 thread_lock(td);
848 resetpriority(td);
849 resetpriority_thread(td);
850 thread_unlock(td);
851 }
852 }
853
854 static void
sched_4bsd_class(struct thread * td,int class)855 sched_4bsd_class(struct thread *td, int class)
856 {
857 THREAD_LOCK_ASSERT(td, MA_OWNED);
858 td->td_pri_class = class;
859 }
860
861 /*
862 * Adjust the priority of a thread.
863 */
864 static void
sched_priority(struct thread * td,u_char prio)865 sched_priority(struct thread *td, u_char prio)
866 {
867
868 KTR_POINT3(KTR_SCHED, "thread", sched_tdname(td), "priority change",
869 "prio:%d", td->td_priority, "new prio:%d", prio, KTR_ATTR_LINKED,
870 sched_tdname(curthread));
871 SDT_PROBE3(sched, , , change__pri, td, td->td_proc, prio);
872 if (td != curthread && prio > td->td_priority) {
873 KTR_POINT3(KTR_SCHED, "thread", sched_tdname(curthread),
874 "lend prio", "prio:%d", td->td_priority, "new prio:%d",
875 prio, KTR_ATTR_LINKED, sched_tdname(td));
876 SDT_PROBE4(sched, , , lend__pri, td, td->td_proc, prio,
877 curthread);
878 }
879 THREAD_LOCK_ASSERT(td, MA_OWNED);
880 if (td->td_priority == prio)
881 return;
882 td->td_priority = prio;
883 if (TD_ON_RUNQ(td) && td->td_rqindex != RQ_PRI_TO_QUEUE_IDX(prio)) {
884 sched_rem(td);
885 sched_add(td, SRQ_BORING | SRQ_HOLDTD);
886 }
887 }
888
889 /*
890 * Update a thread's priority when it is lent another thread's
891 * priority.
892 */
893 static void
sched_4bsd_lend_prio(struct thread * td,u_char prio)894 sched_4bsd_lend_prio(struct thread *td, u_char prio)
895 {
896
897 td->td_flags |= TDF_BORROWING;
898 sched_priority(td, prio);
899 }
900
901 /*
902 * Restore a thread's priority when priority propagation is
903 * over. The prio argument is the minimum priority the thread
904 * needs to have to satisfy other possible priority lending
905 * requests. If the thread's regulary priority is less
906 * important than prio the thread will keep a priority boost
907 * of prio.
908 */
909 static void
sched_4bsd_unlend_prio(struct thread * td,u_char prio)910 sched_4bsd_unlend_prio(struct thread *td, u_char prio)
911 {
912 u_char base_pri;
913
914 if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
915 td->td_base_pri <= PRI_MAX_TIMESHARE)
916 base_pri = td->td_user_pri;
917 else
918 base_pri = td->td_base_pri;
919 if (prio >= base_pri) {
920 td->td_flags &= ~TDF_BORROWING;
921 sched_prio(td, base_pri);
922 } else
923 sched_lend_prio(td, prio);
924 }
925
926 static void
sched_4bsd_prio(struct thread * td,u_char prio)927 sched_4bsd_prio(struct thread *td, u_char prio)
928 {
929 u_char oldprio;
930
931 /* First, update the base priority. */
932 td->td_base_pri = prio;
933
934 /*
935 * If the thread is borrowing another thread's priority, don't ever
936 * lower the priority.
937 */
938 if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
939 return;
940
941 /* Change the real priority. */
942 oldprio = td->td_priority;
943 sched_priority(td, prio);
944
945 /*
946 * If the thread is on a turnstile, then let the turnstile update
947 * its state.
948 */
949 if (TD_ON_LOCK(td) && oldprio != prio)
950 turnstile_adjust(td, oldprio);
951 }
952
953 static void
sched_4bsd_ithread_prio(struct thread * td,u_char prio)954 sched_4bsd_ithread_prio(struct thread *td, u_char prio)
955 {
956 THREAD_LOCK_ASSERT(td, MA_OWNED);
957 MPASS(td->td_pri_class == PRI_ITHD);
958 td->td_base_ithread_pri = prio;
959 sched_prio(td, prio);
960 }
961
962 static void
sched_4bsd_user_prio(struct thread * td,u_char prio)963 sched_4bsd_user_prio(struct thread *td, u_char prio)
964 {
965
966 THREAD_LOCK_ASSERT(td, MA_OWNED);
967 td->td_base_user_pri = prio;
968 if (td->td_lend_user_pri <= prio)
969 return;
970 td->td_user_pri = prio;
971 }
972
973 static void
sched_4bsd_lend_user_prio(struct thread * td,u_char prio)974 sched_4bsd_lend_user_prio(struct thread *td, u_char prio)
975 {
976
977 THREAD_LOCK_ASSERT(td, MA_OWNED);
978 td->td_lend_user_pri = prio;
979 td->td_user_pri = min(prio, td->td_base_user_pri);
980 if (td->td_priority > td->td_user_pri)
981 sched_prio(td, td->td_user_pri);
982 else if (td->td_priority != td->td_user_pri)
983 ast_sched_locked(td, TDA_SCHED);
984 }
985
986 /*
987 * Like the above but first check if there is anything to do.
988 */
989 static void
sched_4bsd_lend_user_prio_cond(struct thread * td,u_char prio)990 sched_4bsd_lend_user_prio_cond(struct thread *td, u_char prio)
991 {
992
993 if (td->td_lend_user_pri == prio)
994 return;
995
996 thread_lock(td);
997 sched_lend_user_prio(td, prio);
998 thread_unlock(td);
999 }
1000
1001 static void
sched_4bsd_sleep(struct thread * td,int pri)1002 sched_4bsd_sleep(struct thread *td, int pri)
1003 {
1004
1005 THREAD_LOCK_ASSERT(td, MA_OWNED);
1006 td->td_slptick = ticks;
1007 td_get_sched(td)->ts_slptime = 0;
1008 if (pri != 0 && PRI_BASE(td->td_pri_class) == PRI_TIMESHARE)
1009 sched_prio(td, pri);
1010 }
1011
1012 static void
sched_4bsd_sswitch(struct thread * td,int flags)1013 sched_4bsd_sswitch(struct thread *td, int flags)
1014 {
1015 struct thread *newtd;
1016 struct mtx *tmtx;
1017 int preempted;
1018
1019 tmtx = &sched_lock;
1020
1021 THREAD_LOCK_ASSERT(td, MA_OWNED);
1022
1023 td->td_lastcpu = td->td_oncpu;
1024 preempted = (td->td_flags & TDF_SLICEEND) == 0 &&
1025 (flags & SW_PREEMPT) != 0;
1026 td->td_flags &= ~TDF_SLICEEND;
1027 ast_unsched_locked(td, TDA_SCHED);
1028 td->td_owepreempt = 0;
1029 td->td_oncpu = NOCPU;
1030
1031 /*
1032 * At the last moment, if this thread is still marked RUNNING,
1033 * then put it back on the run queue as it has not been suspended
1034 * or stopped or any thing else similar. We never put the idle
1035 * threads on the run queue, however.
1036 */
1037 if (td->td_flags & TDF_IDLETD) {
1038 TD_SET_CAN_RUN(td);
1039 #ifdef SMP
1040 CPU_CLR(PCPU_GET(cpuid), &idle_cpus_mask);
1041 #endif
1042 } else {
1043 if (TD_IS_RUNNING(td)) {
1044 /* Put us back on the run queue. */
1045 sched_add(td, SRQ_HOLDTD | SRQ_OURSELF | SRQ_YIELDING |
1046 (preempted ? SRQ_PREEMPTED : 0));
1047 }
1048 }
1049
1050 /*
1051 * Switch to the sched lock to fix things up and pick
1052 * a new thread. Block the td_lock in order to avoid
1053 * breaking the critical path.
1054 */
1055 if (td->td_lock != &sched_lock) {
1056 mtx_lock_spin(&sched_lock);
1057 tmtx = thread_lock_block(td);
1058 mtx_unlock_spin(tmtx);
1059 }
1060
1061 if ((td->td_flags & TDF_NOLOAD) == 0)
1062 sched_load_rem();
1063
1064 newtd = choosethread();
1065 MPASS(newtd->td_lock == &sched_lock);
1066
1067 #if (KTR_COMPILE & KTR_SCHED) != 0
1068 if (TD_IS_IDLETHREAD(td))
1069 KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "idle",
1070 "prio:%d", td->td_priority);
1071 else
1072 KTR_STATE3(KTR_SCHED, "thread", sched_tdname(td), KTDSTATE(td),
1073 "prio:%d", td->td_priority, "wmesg:\"%s\"", td->td_wmesg,
1074 "lockname:\"%s\"", td->td_lockname);
1075 #endif
1076
1077 if (td != newtd) {
1078 #ifdef HWPMC_HOOKS
1079 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1080 PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
1081 #endif
1082
1083 #ifdef HWT_HOOKS
1084 HWT_CALL_HOOK(td, HWT_SWITCH_OUT, NULL);
1085 HWT_CALL_HOOK(newtd, HWT_SWITCH_IN, NULL);
1086 #endif
1087
1088 SDT_PROBE2(sched, , , off__cpu, newtd, newtd->td_proc);
1089
1090 /* I feel sleepy */
1091 lock_profile_release_lock(&sched_lock.lock_object, true);
1092 #ifdef KDTRACE_HOOKS
1093 /*
1094 * If DTrace has set the active vtime enum to anything
1095 * other than INACTIVE (0), then it should have set the
1096 * function to call.
1097 */
1098 if (dtrace_vtime_active)
1099 (*dtrace_vtime_switch_func)(newtd);
1100 #endif
1101
1102 cpu_switch(td, newtd, tmtx);
1103 lock_profile_obtain_lock_success(&sched_lock.lock_object, true,
1104 0, 0, __FILE__, __LINE__);
1105 /*
1106 * Where am I? What year is it?
1107 * We are in the same thread that went to sleep above,
1108 * but any amount of time may have passed. All our context
1109 * will still be available as will local variables.
1110 * PCPU values however may have changed as we may have
1111 * changed CPU so don't trust cached values of them.
1112 * New threads will go to fork_exit() instead of here
1113 * so if you change things here you may need to change
1114 * things there too.
1115 *
1116 * If the thread above was exiting it will never wake
1117 * up again here, so either it has saved everything it
1118 * needed to, or the thread_wait() or wait() will
1119 * need to reap it.
1120 */
1121
1122 SDT_PROBE0(sched, , , on__cpu);
1123 #ifdef HWPMC_HOOKS
1124 if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1125 PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
1126 #endif
1127 } else {
1128 td->td_lock = &sched_lock;
1129 SDT_PROBE0(sched, , , remain__cpu);
1130 }
1131
1132 KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "running",
1133 "prio:%d", td->td_priority);
1134
1135 #ifdef SMP
1136 if (td->td_flags & TDF_IDLETD)
1137 CPU_SET(PCPU_GET(cpuid), &idle_cpus_mask);
1138 #endif
1139 sched_lock.mtx_lock = (uintptr_t)td;
1140 td->td_oncpu = PCPU_GET(cpuid);
1141 spinlock_enter();
1142 mtx_unlock_spin(&sched_lock);
1143 }
1144
1145 static void
sched_4bsd_wakeup(struct thread * td,int srqflags)1146 sched_4bsd_wakeup(struct thread *td, int srqflags)
1147 {
1148 struct td_sched *ts;
1149
1150 THREAD_LOCK_ASSERT(td, MA_OWNED);
1151 ts = td_get_sched(td);
1152 if (ts->ts_slptime > 1) {
1153 updatepri(td);
1154 resetpriority(td);
1155 }
1156 td->td_slptick = 0;
1157 ts->ts_slptime = 0;
1158 ts->ts_slice = sched_slice;
1159
1160 /*
1161 * When resuming an idle ithread, restore its base ithread
1162 * priority.
1163 */
1164 if (PRI_BASE(td->td_pri_class) == PRI_ITHD &&
1165 td->td_base_pri != td->td_base_ithread_pri)
1166 sched_prio(td, td->td_base_ithread_pri);
1167
1168 sched_add(td, srqflags);
1169 }
1170
1171 #ifdef SMP
1172 static int
forward_wakeup(int cpunum)1173 forward_wakeup(int cpunum)
1174 {
1175 struct pcpu *pc;
1176 cpuset_t dontuse, map, map2;
1177 u_int id, me;
1178 int iscpuset;
1179
1180 mtx_assert(&sched_lock, MA_OWNED);
1181
1182 CTR0(KTR_RUNQ, "forward_wakeup()");
1183
1184 if ((!forward_wakeup_enabled) ||
1185 (forward_wakeup_use_mask == 0 && forward_wakeup_use_loop == 0))
1186 return (0);
1187 if (!smp_started || KERNEL_PANICKED())
1188 return (0);
1189
1190 forward_wakeups_requested++;
1191
1192 /*
1193 * Check the idle mask we received against what we calculated
1194 * before in the old version.
1195 */
1196 me = PCPU_GET(cpuid);
1197
1198 /* Don't bother if we should be doing it ourself. */
1199 if (CPU_ISSET(me, &idle_cpus_mask) &&
1200 (cpunum == NOCPU || me == cpunum))
1201 return (0);
1202
1203 CPU_SETOF(me, &dontuse);
1204 CPU_OR(&dontuse, &dontuse, &stopped_cpus);
1205 CPU_ZERO(&map2);
1206 if (forward_wakeup_use_loop) {
1207 STAILQ_FOREACH(pc, &cpuhead, pc_allcpu) {
1208 id = pc->pc_cpuid;
1209 if (!CPU_ISSET(id, &dontuse) &&
1210 pc->pc_curthread == pc->pc_idlethread) {
1211 CPU_SET(id, &map2);
1212 }
1213 }
1214 }
1215
1216 if (forward_wakeup_use_mask) {
1217 map = idle_cpus_mask;
1218 CPU_ANDNOT(&map, &map, &dontuse);
1219
1220 /* If they are both on, compare and use loop if different. */
1221 if (forward_wakeup_use_loop) {
1222 if (CPU_CMP(&map, &map2)) {
1223 printf("map != map2, loop method preferred\n");
1224 map = map2;
1225 }
1226 }
1227 } else {
1228 map = map2;
1229 }
1230
1231 /* If we only allow a specific CPU, then mask off all the others. */
1232 if (cpunum != NOCPU) {
1233 KASSERT((cpunum <= mp_maxcpus),("forward_wakeup: bad cpunum."));
1234 iscpuset = CPU_ISSET(cpunum, &map);
1235 if (iscpuset == 0)
1236 CPU_ZERO(&map);
1237 else
1238 CPU_SETOF(cpunum, &map);
1239 }
1240 if (!CPU_EMPTY(&map)) {
1241 forward_wakeups_delivered++;
1242 STAILQ_FOREACH(pc, &cpuhead, pc_allcpu) {
1243 id = pc->pc_cpuid;
1244 if (!CPU_ISSET(id, &map))
1245 continue;
1246 if (cpu_idle_wakeup(pc->pc_cpuid))
1247 CPU_CLR(id, &map);
1248 }
1249 if (!CPU_EMPTY(&map))
1250 ipi_selected(map, IPI_AST);
1251 return (1);
1252 }
1253 if (cpunum == NOCPU)
1254 printf("forward_wakeup: Idle processor not found\n");
1255 return (0);
1256 }
1257
1258 static void
kick_other_cpu(int pri,int cpuid)1259 kick_other_cpu(int pri, int cpuid)
1260 {
1261 struct pcpu *pcpu;
1262 int cpri;
1263
1264 pcpu = pcpu_find(cpuid);
1265 if (CPU_ISSET(cpuid, &idle_cpus_mask)) {
1266 forward_wakeups_delivered++;
1267 if (!cpu_idle_wakeup(cpuid))
1268 ipi_cpu(cpuid, IPI_AST);
1269 return;
1270 }
1271
1272 cpri = pcpu->pc_curthread->td_priority;
1273 if (pri >= cpri)
1274 return;
1275
1276 #if defined(IPI_PREEMPTION) && defined(PREEMPTION)
1277 #if !defined(FULL_PREEMPTION)
1278 if (pri <= PRI_MAX_ITHD)
1279 #endif /* ! FULL_PREEMPTION */
1280 {
1281 ipi_cpu(cpuid, IPI_PREEMPT);
1282 return;
1283 }
1284 #endif /* defined(IPI_PREEMPTION) && defined(PREEMPTION) */
1285
1286 if (pcpu->pc_curthread->td_lock == &sched_lock) {
1287 ast_sched_locked(pcpu->pc_curthread, TDA_SCHED);
1288 ipi_cpu(cpuid, IPI_AST);
1289 }
1290 }
1291 #endif /* SMP */
1292
1293 #ifdef SMP
1294 static int
sched_pickcpu(struct thread * td)1295 sched_pickcpu(struct thread *td)
1296 {
1297 int best, cpu;
1298
1299 mtx_assert(&sched_lock, MA_OWNED);
1300
1301 if (td->td_lastcpu != NOCPU && THREAD_CAN_SCHED(td, td->td_lastcpu))
1302 best = td->td_lastcpu;
1303 else
1304 best = NOCPU;
1305 CPU_FOREACH(cpu) {
1306 if (!THREAD_CAN_SCHED(td, cpu))
1307 continue;
1308
1309 if (best == NOCPU)
1310 best = cpu;
1311 else if (DPCPU_ID_GET(cpu, runq_length) < DPCPU_ID_GET(best, runq_length))
1312 best = cpu;
1313 }
1314 KASSERT(best != NOCPU, ("no valid CPUs"));
1315
1316 return (best);
1317 }
1318 #endif
1319
1320 static void
sched_4bsd_add(struct thread * td,int flags)1321 sched_4bsd_add(struct thread *td, int flags)
1322 #ifdef SMP
1323 {
1324 cpuset_t tidlemsk;
1325 struct td_sched *ts;
1326 u_int cpu, cpuid;
1327 int forwarded = 0;
1328 int single_cpu = 0;
1329
1330 ts = td_get_sched(td);
1331 THREAD_LOCK_ASSERT(td, MA_OWNED);
1332 KASSERT((td->td_inhibitors == 0),
1333 ("sched_add: trying to run inhibited thread"));
1334 KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
1335 ("sched_add: bad thread state"));
1336 KASSERT(td->td_flags & TDF_INMEM,
1337 ("sched_add: thread swapped out"));
1338
1339 KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq add",
1340 "prio:%d", td->td_priority, KTR_ATTR_LINKED,
1341 sched_tdname(curthread));
1342 KTR_POINT1(KTR_SCHED, "thread", sched_tdname(curthread), "wokeup",
1343 KTR_ATTR_LINKED, sched_tdname(td));
1344 SDT_PROBE4(sched, , , enqueue, td, td->td_proc, NULL,
1345 flags & SRQ_PREEMPTED);
1346
1347 /*
1348 * Now that the thread is moving to the run-queue, set the lock
1349 * to the scheduler's lock.
1350 */
1351 if (td->td_lock != &sched_lock) {
1352 mtx_lock_spin(&sched_lock);
1353 if ((flags & SRQ_HOLD) != 0)
1354 td->td_lock = &sched_lock;
1355 else
1356 thread_lock_set(td, &sched_lock);
1357 }
1358 TD_SET_RUNQ(td);
1359
1360 /*
1361 * If SMP is started and the thread is pinned or otherwise limited to
1362 * a specific set of CPUs, queue the thread to a per-CPU run queue.
1363 * Otherwise, queue the thread to the global run queue.
1364 *
1365 * If SMP has not yet been started we must use the global run queue
1366 * as per-CPU state may not be initialized yet and we may crash if we
1367 * try to access the per-CPU run queues.
1368 */
1369 if (smp_started && (td->td_pinned != 0 || td->td_flags & TDF_BOUND ||
1370 ts->ts_flags & TSF_AFFINITY)) {
1371 if (td->td_pinned != 0)
1372 cpu = td->td_lastcpu;
1373 else if (td->td_flags & TDF_BOUND) {
1374 /* Find CPU from bound runq. */
1375 KASSERT(ts->ts_rqcpu != NOCPU,
1376 ("sched_add: bound td_sched not on cpu runq"));
1377 cpu = ts->ts_rqcpu;
1378 } else
1379 /* Find a valid CPU for our cpuset */
1380 cpu = sched_pickcpu(td);
1381 ts->ts_rqcpu = cpu;
1382 single_cpu = 1;
1383 CTR3(KTR_RUNQ,
1384 "sched_add: Put td_sched:%p(td:%p) on cpu%d runq", ts, td,
1385 cpu);
1386 } else {
1387 CTR2(KTR_RUNQ,
1388 "sched_add: adding td_sched:%p (td:%p) to gbl runq", ts,
1389 td);
1390 cpu = NOCPU;
1391 ts->ts_rqcpu = NOCPU;
1392 }
1393
1394 if ((td->td_flags & TDF_NOLOAD) == 0)
1395 sched_load_add();
1396 runq_add(TS_RUNQ_PTR(ts), td, flags);
1397 if (cpu != NOCPU)
1398 (*DPCPU_ID_PTR(cpu, runq_length))++;
1399
1400 cpuid = PCPU_GET(cpuid);
1401 if (single_cpu && cpu != cpuid) {
1402 kick_other_cpu(td->td_priority, cpu);
1403 } else {
1404 if (!single_cpu) {
1405 tidlemsk = idle_cpus_mask;
1406 CPU_CLR(cpuid, &tidlemsk);
1407
1408 if (!CPU_ISSET(cpuid, &idle_cpus_mask) &&
1409 ((flags & SRQ_INTR) == 0) &&
1410 !CPU_EMPTY(&tidlemsk))
1411 forwarded = forward_wakeup(cpu);
1412 }
1413
1414 if (!forwarded) {
1415 if (!maybe_preempt(td))
1416 maybe_resched(td);
1417 }
1418 }
1419 if ((flags & SRQ_HOLDTD) == 0)
1420 thread_unlock(td);
1421 }
1422 #else /* SMP */
1423 {
1424 struct td_sched *ts;
1425
1426 ts = td_get_sched(td);
1427 THREAD_LOCK_ASSERT(td, MA_OWNED);
1428 KASSERT((td->td_inhibitors == 0),
1429 ("sched_add: trying to run inhibited thread"));
1430 KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
1431 ("sched_add: bad thread state"));
1432 KASSERT(td->td_flags & TDF_INMEM,
1433 ("sched_add: thread swapped out"));
1434 KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq add",
1435 "prio:%d", td->td_priority, KTR_ATTR_LINKED,
1436 sched_tdname(curthread));
1437 KTR_POINT1(KTR_SCHED, "thread", sched_tdname(curthread), "wokeup",
1438 KTR_ATTR_LINKED, sched_tdname(td));
1439 SDT_PROBE4(sched, , , enqueue, td, td->td_proc, NULL,
1440 flags & SRQ_PREEMPTED);
1441
1442 /*
1443 * Now that the thread is moving to the run-queue, set the lock
1444 * to the scheduler's lock.
1445 */
1446 if (td->td_lock != &sched_lock) {
1447 mtx_lock_spin(&sched_lock);
1448 if ((flags & SRQ_HOLD) != 0)
1449 td->td_lock = &sched_lock;
1450 else
1451 thread_lock_set(td, &sched_lock);
1452 }
1453 TD_SET_RUNQ(td);
1454 CTR2(KTR_RUNQ, "sched_add: adding td_sched:%p (td:%p) to runq", ts, td);
1455 ts->ts_rqcpu = NOCPU;
1456
1457 if ((td->td_flags & TDF_NOLOAD) == 0)
1458 sched_load_add();
1459 runq_add(TS_RUNQ_PTR(ts), td, flags);
1460 if (!maybe_preempt(td))
1461 maybe_resched(td);
1462 if ((flags & SRQ_HOLDTD) == 0)
1463 thread_unlock(td);
1464 }
1465 #endif /* SMP */
1466
1467 static void
sched_4bsd_rem(struct thread * td)1468 sched_4bsd_rem(struct thread *td)
1469 {
1470 struct td_sched *ts;
1471
1472 ts = td_get_sched(td);
1473 KASSERT(td->td_flags & TDF_INMEM,
1474 ("sched_rem: thread swapped out"));
1475 KASSERT(TD_ON_RUNQ(td),
1476 ("sched_rem: thread not on run queue"));
1477 mtx_assert(&sched_lock, MA_OWNED);
1478 KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq rem",
1479 "prio:%d", td->td_priority, KTR_ATTR_LINKED,
1480 sched_tdname(curthread));
1481 SDT_PROBE3(sched, , , dequeue, td, td->td_proc, NULL);
1482
1483 if ((td->td_flags & TDF_NOLOAD) == 0)
1484 sched_load_rem();
1485 #ifdef SMP
1486 if (ts->ts_rqcpu != NOCPU)
1487 (*DPCPU_ID_PTR(ts->ts_rqcpu, runq_length))--;
1488 #endif
1489 runq_remove(TS_RUNQ_PTR(ts), td);
1490 TD_SET_CAN_RUN(td);
1491 }
1492
1493 /*
1494 * Select threads to run. Note that running threads still consume a
1495 * slot.
1496 */
1497 static struct thread *
sched_4bsd_choose(void)1498 sched_4bsd_choose(void)
1499 {
1500 struct thread *td;
1501 struct runq *runq;
1502
1503 mtx_assert(&sched_lock, MA_OWNED);
1504 #ifdef SMP
1505 struct thread *tdcpu;
1506
1507 runq = &runq_global;
1508 td = runq_choose_fuzz(&runq_global, runq_fuzz);
1509 tdcpu = runq_choose(DPCPU_PTR(runq_pcpu));
1510
1511 if (td == NULL ||
1512 (tdcpu != NULL &&
1513 tdcpu->td_priority < td->td_priority)) {
1514 CTR2(KTR_RUNQ, "choosing td %p from pcpu runq %d", tdcpu,
1515 PCPU_GET(cpuid));
1516 td = tdcpu;
1517 runq = DPCPU_PTR(runq_pcpu);
1518 } else {
1519 CTR1(KTR_RUNQ, "choosing td_sched %p from main runq", td);
1520 }
1521
1522 #else
1523 runq = &runq_global;
1524 td = runq_choose(&runq_global);
1525 #endif
1526
1527 if (td) {
1528 #ifdef SMP
1529 if (td == tdcpu)
1530 (*DPCPU_PTR(runq_length))--;
1531 #endif
1532 runq_remove(runq, td);
1533 td->td_flags |= TDF_DIDRUN;
1534
1535 KASSERT(td->td_flags & TDF_INMEM,
1536 ("sched_choose: thread swapped out"));
1537 return (td);
1538 }
1539 return (PCPU_GET(idlethread));
1540 }
1541
1542 static void
sched_4bsd_preempt(struct thread * td)1543 sched_4bsd_preempt(struct thread *td)
1544 {
1545 int flags;
1546
1547 SDT_PROBE2(sched, , , surrender, td, td->td_proc);
1548 if (td->td_critnest > 1) {
1549 td->td_owepreempt = 1;
1550 } else {
1551 thread_lock(td);
1552 flags = SW_INVOL | SW_PREEMPT;
1553 flags |= TD_IS_IDLETHREAD(td) ? SWT_REMOTEWAKEIDLE :
1554 SWT_REMOTEPREEMPT;
1555 mi_switch(flags);
1556 }
1557 }
1558
1559 static void
sched_4bsd_userret_slowpath(struct thread * td)1560 sched_4bsd_userret_slowpath(struct thread *td)
1561 {
1562
1563 thread_lock(td);
1564 td->td_priority = td->td_user_pri;
1565 td->td_base_pri = td->td_user_pri;
1566 thread_unlock(td);
1567 }
1568
1569 static void
sched_4bsd_bind(struct thread * td,int cpu)1570 sched_4bsd_bind(struct thread *td, int cpu)
1571 {
1572 #ifdef SMP
1573 struct td_sched *ts = td_get_sched(td);
1574 #endif
1575
1576 THREAD_LOCK_ASSERT(td, MA_OWNED|MA_NOTRECURSED);
1577 KASSERT(td == curthread, ("sched_bind: can only bind curthread"));
1578
1579 td->td_flags |= TDF_BOUND;
1580 #ifdef SMP
1581 ts->ts_rqcpu = cpu;
1582 if (PCPU_GET(cpuid) == cpu)
1583 return;
1584
1585 mi_switch(SW_VOL | SWT_BIND);
1586 thread_lock(td);
1587 #endif
1588 }
1589
1590 static void
sched_4bsd_unbind(struct thread * td)1591 sched_4bsd_unbind(struct thread* td)
1592 {
1593 THREAD_LOCK_ASSERT(td, MA_OWNED);
1594 KASSERT(td == curthread, ("sched_unbind: can only bind curthread"));
1595 td->td_flags &= ~TDF_BOUND;
1596 }
1597
1598 static int
sched_4bsd_is_bound(struct thread * td)1599 sched_4bsd_is_bound(struct thread *td)
1600 {
1601 THREAD_LOCK_ASSERT(td, MA_OWNED);
1602 return (td->td_flags & TDF_BOUND);
1603 }
1604
1605 static void
sched_4bsd_relinquish(struct thread * td)1606 sched_4bsd_relinquish(struct thread *td)
1607 {
1608 thread_lock(td);
1609 mi_switch(SW_VOL | SWT_RELINQUISH);
1610 }
1611
1612 static int
sched_4bsd_load(void)1613 sched_4bsd_load(void)
1614 {
1615 return (sched_tdcnt);
1616 }
1617
1618 static int
sched_4bsd_sizeof_proc(void)1619 sched_4bsd_sizeof_proc(void)
1620 {
1621 return (sizeof(struct proc));
1622 }
1623
1624 static int
sched_4bsd_sizeof_thread(void)1625 sched_4bsd_sizeof_thread(void)
1626 {
1627 return (sizeof(struct thread) + sizeof(struct td_sched));
1628 }
1629
1630 static fixpt_t
sched_4bsd_pctcpu(struct thread * td)1631 sched_4bsd_pctcpu(struct thread *td)
1632 {
1633 struct td_sched *ts;
1634
1635 THREAD_LOCK_ASSERT(td, MA_OWNED);
1636 ts = td_get_sched(td);
1637 return (ts->ts_pctcpu);
1638 }
1639
1640 static u_int
sched_4bsd_estcpu(struct thread * td)1641 sched_4bsd_estcpu(struct thread *td)
1642 {
1643
1644 return (td_get_sched(td)->ts_estcpu);
1645 }
1646
1647 /*
1648 * The actual idle process.
1649 */
1650 static void
sched_4bsd_idletd(void * dummy)1651 sched_4bsd_idletd(void *dummy)
1652 {
1653 struct pcpuidlestat *stat;
1654
1655 THREAD_NO_SLEEPING();
1656 stat = DPCPU_PTR(idlestat);
1657 for (;;) {
1658 mtx_assert(&Giant, MA_NOTOWNED);
1659
1660 while (!sched_runnable()) {
1661 cpu_idle(stat->idlecalls + stat->oldidlecalls > 64);
1662 stat->idlecalls++;
1663 }
1664
1665 mtx_lock_spin(&sched_lock);
1666 mi_switch(SW_VOL | SWT_IDLE);
1667 }
1668 }
1669
1670 static void
sched_throw_tail(struct thread * td)1671 sched_throw_tail(struct thread *td)
1672 {
1673 struct thread *newtd;
1674
1675 mtx_assert(&sched_lock, MA_OWNED);
1676 KASSERT(curthread->td_md.md_spinlock_count == 1, ("invalid count"));
1677
1678 newtd = choosethread();
1679
1680 #ifdef HWT_HOOKS
1681 if (td)
1682 HWT_CALL_HOOK(td, HWT_SWITCH_OUT, NULL);
1683 HWT_CALL_HOOK(newtd, HWT_SWITCH_IN, NULL);
1684 #endif
1685
1686 cpu_throw(td, newtd); /* doesn't return */
1687 }
1688
1689 /*
1690 * A CPU is entering for the first time.
1691 */
1692 static void
sched_4bsd_ap_entry(void)1693 sched_4bsd_ap_entry(void)
1694 {
1695
1696 /*
1697 * Correct spinlock nesting. The idle thread context that we are
1698 * borrowing was created so that it would start out with a single
1699 * spin lock (sched_lock) held in fork_trampoline(). Since we've
1700 * explicitly acquired locks in this function, the nesting count
1701 * is now 2 rather than 1. Since we are nested, calling
1702 * spinlock_exit() will simply adjust the counts without allowing
1703 * spin lock using code to interrupt us.
1704 */
1705 mtx_lock_spin(&sched_lock);
1706 spinlock_exit();
1707 PCPU_SET(switchtime, cpu_ticks());
1708 PCPU_SET(switchticks, ticks);
1709
1710 sched_throw_tail(NULL);
1711 }
1712
1713 /*
1714 * A thread is exiting.
1715 */
1716 static void
sched_4bsd_throw(struct thread * td)1717 sched_4bsd_throw(struct thread *td)
1718 {
1719
1720 MPASS(td != NULL);
1721 MPASS(td->td_lock == &sched_lock);
1722
1723 lock_profile_release_lock(&sched_lock.lock_object, true);
1724 td->td_lastcpu = td->td_oncpu;
1725 td->td_oncpu = NOCPU;
1726
1727 sched_throw_tail(td);
1728 }
1729
1730 static void
sched_4bsd_fork_exit(struct thread * td)1731 sched_4bsd_fork_exit(struct thread *td)
1732 {
1733
1734 /*
1735 * Finish setting up thread glue so that it begins execution in a
1736 * non-nested critical section with sched_lock held but not recursed.
1737 */
1738 td->td_oncpu = PCPU_GET(cpuid);
1739 sched_lock.mtx_lock = (uintptr_t)td;
1740 lock_profile_obtain_lock_success(&sched_lock.lock_object, true,
1741 0, 0, __FILE__, __LINE__);
1742 THREAD_LOCK_ASSERT(td, MA_OWNED | MA_NOTRECURSED);
1743
1744 KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "running",
1745 "prio:%d", td->td_priority);
1746 SDT_PROBE0(sched, , , on__cpu);
1747 }
1748
1749 static char *
sched_4bsd_tdname(struct thread * td)1750 sched_4bsd_tdname(struct thread *td)
1751 {
1752 #ifdef KTR
1753 struct td_sched *ts;
1754
1755 ts = td_get_sched(td);
1756 if (ts->ts_name[0] == '\0')
1757 snprintf(ts->ts_name, sizeof(ts->ts_name),
1758 "%s tid %d", td->td_name, td->td_tid);
1759 return (ts->ts_name);
1760 #else
1761 return (td->td_name);
1762 #endif
1763 }
1764
1765 static void
sched_4bsd_clear_tdname(struct thread * td)1766 sched_4bsd_clear_tdname(struct thread *td)
1767 {
1768 #ifdef KTR
1769 struct td_sched *ts;
1770
1771 ts = td_get_sched(td);
1772 ts->ts_name[0] = '\0';
1773 #endif
1774 }
1775
1776 static void
sched_4bsd_affinity(struct thread * td)1777 sched_4bsd_affinity(struct thread *td)
1778 {
1779 #ifdef SMP
1780 struct td_sched *ts;
1781 int cpu;
1782
1783 THREAD_LOCK_ASSERT(td, MA_OWNED);
1784
1785 /*
1786 * Set the TSF_AFFINITY flag if there is at least one CPU this
1787 * thread can't run on.
1788 */
1789 ts = td_get_sched(td);
1790 ts->ts_flags &= ~TSF_AFFINITY;
1791 CPU_FOREACH(cpu) {
1792 if (!THREAD_CAN_SCHED(td, cpu)) {
1793 ts->ts_flags |= TSF_AFFINITY;
1794 break;
1795 }
1796 }
1797
1798 /*
1799 * If this thread can run on all CPUs, nothing else to do.
1800 */
1801 if (!(ts->ts_flags & TSF_AFFINITY))
1802 return;
1803
1804 /* Pinned threads and bound threads should be left alone. */
1805 if (td->td_pinned != 0 || td->td_flags & TDF_BOUND)
1806 return;
1807
1808 switch (TD_GET_STATE(td)) {
1809 case TDS_RUNQ:
1810 /*
1811 * If we are on a per-CPU runqueue that is in the set,
1812 * then nothing needs to be done.
1813 */
1814 if (ts->ts_rqcpu != NOCPU && THREAD_CAN_SCHED(td, ts->ts_rqcpu))
1815 return;
1816
1817 /* Put this thread on a valid per-CPU runqueue. */
1818 sched_rem(td);
1819 sched_add(td, SRQ_HOLDTD | SRQ_BORING);
1820 break;
1821 case TDS_RUNNING:
1822 /*
1823 * See if our current CPU is in the set. If not, force a
1824 * context switch.
1825 */
1826 if (THREAD_CAN_SCHED(td, td->td_oncpu))
1827 return;
1828
1829 ast_sched_locked(td, TDA_SCHED);
1830 if (td != curthread)
1831 ipi_cpu(cpu, IPI_AST);
1832 break;
1833 default:
1834 break;
1835 }
1836 #endif
1837 }
1838
1839 static int
sched_4bsd_find_l2_neighbor(int cpu)1840 sched_4bsd_find_l2_neighbor(int cpu)
1841 {
1842 return (-1);
1843 }
1844
1845 struct sched_instance sched_4bsd_instance = {
1846 #define SLOT(name) .name = sched_4bsd_##name
1847 SLOT(load),
1848 SLOT(rr_interval),
1849 SLOT(runnable),
1850 SLOT(exit),
1851 SLOT(fork),
1852 SLOT(fork_exit),
1853 SLOT(class),
1854 SLOT(nice),
1855 SLOT(ap_entry),
1856 SLOT(exit_thread),
1857 SLOT(estcpu),
1858 SLOT(fork_thread),
1859 SLOT(ithread_prio),
1860 SLOT(lend_prio),
1861 SLOT(lend_user_prio),
1862 SLOT(lend_user_prio_cond),
1863 SLOT(pctcpu),
1864 SLOT(prio),
1865 SLOT(sleep),
1866 SLOT(sswitch),
1867 SLOT(throw),
1868 SLOT(unlend_prio),
1869 SLOT(user_prio),
1870 SLOT(userret_slowpath),
1871 SLOT(add),
1872 SLOT(choose),
1873 SLOT(clock),
1874 SLOT(idletd),
1875 SLOT(preempt),
1876 SLOT(relinquish),
1877 SLOT(rem),
1878 SLOT(wakeup),
1879 SLOT(bind),
1880 SLOT(unbind),
1881 SLOT(is_bound),
1882 SLOT(affinity),
1883 SLOT(sizeof_proc),
1884 SLOT(sizeof_thread),
1885 SLOT(tdname),
1886 SLOT(clear_tdname),
1887 SLOT(find_l2_neighbor),
1888 SLOT(init),
1889 SLOT(init_ap),
1890 SLOT(setup),
1891 SLOT(initticks),
1892 SLOT(sysinit),
1893 #undef SLOT
1894 };
1895 DECLARE_SCHEDULER(fourbsd_sched_selector, "4BSD", &sched_4bsd_instance);
1896