1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29 #include <sys/cdefs.h>
30 #include "opt_sched.h"
31
32 #include <sys/param.h>
33 #include <sys/systm.h>
34 #include <sys/kdb.h>
35 #include <sys/kernel.h>
36 #include <sys/ktr.h>
37 #include <sys/lock.h>
38 #include <sys/mutex.h>
39 #include <sys/proc.h>
40 #include <sys/queue.h>
41 #include <sys/sched.h>
42 #include <sys/smp.h>
43 #include <sys/sysctl.h>
44
45 #include <machine/cpu.h>
46
47 /* Uncomment this to enable logging of critical_enter/exit. */
48 #if 0
49 #define KTR_CRITICAL KTR_SCHED
50 #else
51 #define KTR_CRITICAL 0
52 #endif
53
54 #ifdef FULL_PREEMPTION
55 #ifndef PREEMPTION
56 #error "The FULL_PREEMPTION option requires the PREEMPTION option"
57 #endif
58 #endif
59
60 CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS);
61
62 /*
63 * kern.sched.preemption allows user space to determine if preemption support
64 * is compiled in or not. It is not currently a boot or runtime flag that
65 * can be changed.
66 */
67 #ifdef PREEMPTION
68 static int kern_sched_preemption = 1;
69 #else
70 static int kern_sched_preemption = 0;
71 #endif
72 SYSCTL_INT(_kern_sched, OID_AUTO, preemption, CTLFLAG_RD,
73 &kern_sched_preemption, 0, "Kernel preemption enabled");
74
75 /*
76 * Support for scheduler stats exported via kern.sched.stats. All stats may
77 * be reset with kern.sched.stats.reset = 1. Stats may be defined elsewhere
78 * with SCHED_STAT_DEFINE().
79 */
80 #ifdef SCHED_STATS
81 SYSCTL_NODE(_kern_sched, OID_AUTO, stats, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
82 "switch stats");
83
84 /* Switch reasons from mi_switch(). */
85 DPCPU_DEFINE(long, sched_switch_stats[SWT_COUNT]);
86 SCHED_STAT_DEFINE_VAR(uncategorized,
87 &DPCPU_NAME(sched_switch_stats[SWT_NONE]), "");
88 SCHED_STAT_DEFINE_VAR(preempt,
89 &DPCPU_NAME(sched_switch_stats[SWT_PREEMPT]), "");
90 SCHED_STAT_DEFINE_VAR(owepreempt,
91 &DPCPU_NAME(sched_switch_stats[SWT_OWEPREEMPT]), "");
92 SCHED_STAT_DEFINE_VAR(turnstile,
93 &DPCPU_NAME(sched_switch_stats[SWT_TURNSTILE]), "");
94 SCHED_STAT_DEFINE_VAR(sleepq,
95 &DPCPU_NAME(sched_switch_stats[SWT_SLEEPQ]), "");
96 SCHED_STAT_DEFINE_VAR(sleepqtimo,
97 &DPCPU_NAME(sched_switch_stats[SWT_SLEEPQTIMO]), "");
98 SCHED_STAT_DEFINE_VAR(relinquish,
99 &DPCPU_NAME(sched_switch_stats[SWT_RELINQUISH]), "");
100 SCHED_STAT_DEFINE_VAR(needresched,
101 &DPCPU_NAME(sched_switch_stats[SWT_NEEDRESCHED]), "");
102 SCHED_STAT_DEFINE_VAR(idle,
103 &DPCPU_NAME(sched_switch_stats[SWT_IDLE]), "");
104 SCHED_STAT_DEFINE_VAR(iwait,
105 &DPCPU_NAME(sched_switch_stats[SWT_IWAIT]), "");
106 SCHED_STAT_DEFINE_VAR(suspend,
107 &DPCPU_NAME(sched_switch_stats[SWT_SUSPEND]), "");
108 SCHED_STAT_DEFINE_VAR(remotepreempt,
109 &DPCPU_NAME(sched_switch_stats[SWT_REMOTEPREEMPT]), "");
110 SCHED_STAT_DEFINE_VAR(remotewakeidle,
111 &DPCPU_NAME(sched_switch_stats[SWT_REMOTEWAKEIDLE]), "");
112
113 static int
sysctl_stats_reset(SYSCTL_HANDLER_ARGS)114 sysctl_stats_reset(SYSCTL_HANDLER_ARGS)
115 {
116 struct sysctl_oid *p;
117 uintptr_t counter;
118 int error;
119 int val;
120 int i;
121
122 val = 0;
123 error = sysctl_handle_int(oidp, &val, 0, req);
124 if (error != 0 || req->newptr == NULL)
125 return (error);
126 if (val == 0)
127 return (0);
128 /*
129 * Traverse the list of children of _kern_sched_stats and reset each
130 * to 0. Skip the reset entry.
131 */
132 SLIST_FOREACH(p, oidp->oid_parent, oid_link) {
133 if (p == oidp || p->oid_arg1 == NULL)
134 continue;
135 counter = (uintptr_t)p->oid_arg1;
136 CPU_FOREACH(i) {
137 *(long *)(dpcpu_off[i] + counter) = 0;
138 }
139 }
140 return (0);
141 }
142
143 SYSCTL_PROC(_kern_sched_stats, OID_AUTO, reset,
144 CTLTYPE_INT | CTLFLAG_WR | CTLFLAG_MPSAFE, NULL, 0,
145 sysctl_stats_reset, "I",
146 "Reset scheduler statistics");
147 #endif
148
149 /************************************************************************
150 * Functions that manipulate runnability from a thread perspective. *
151 ************************************************************************/
152 /*
153 * Select the thread that will be run next.
154 */
155
156 static __noinline struct thread *
choosethread_panic(struct thread * td)157 choosethread_panic(struct thread *td)
158 {
159
160 /*
161 * If we are in panic, only allow system threads,
162 * plus the one we are running in, to be run.
163 */
164 retry:
165 if (((td->td_proc->p_flag & P_SYSTEM) == 0 &&
166 (td->td_flags & TDF_INPANIC) == 0)) {
167 /* note that it is no longer on the run queue */
168 TD_SET_CAN_RUN(td);
169 td = sched_choose();
170 goto retry;
171 }
172
173 TD_SET_RUNNING(td);
174 return (td);
175 }
176
177 struct thread *
choosethread(void)178 choosethread(void)
179 {
180 struct thread *td;
181
182 td = sched_choose();
183
184 if (KERNEL_PANICKED())
185 return (choosethread_panic(td));
186
187 TD_SET_RUNNING(td);
188 return (td);
189 }
190
191 /*
192 * Kernel thread preemption implementation. Critical sections mark
193 * regions of code in which preemptions are not allowed.
194 *
195 * It might seem a good idea to inline critical_enter() but, in order
196 * to prevent instructions reordering by the compiler, a __compiler_membar()
197 * would have to be used here (the same as sched_pin()). The performance
198 * penalty imposed by the membar could, then, produce slower code than
199 * the function call itself, for most cases.
200 */
201 void
critical_enter_KBI(void)202 critical_enter_KBI(void)
203 {
204 #ifdef KTR
205 struct thread *td = curthread;
206 #endif
207 critical_enter();
208 CTR4(KTR_CRITICAL, "critical_enter by thread %p (%ld, %s) to %d", td,
209 (long)td->td_proc->p_pid, td->td_name, td->td_critnest);
210 }
211
212 void __noinline
critical_exit_preempt(void)213 critical_exit_preempt(void)
214 {
215 struct thread *td;
216 int flags;
217
218 /*
219 * If td_critnest is 0, it is possible that we are going to get
220 * preempted again before reaching the code below. This happens
221 * rarely and is harmless. However, this means td_owepreempt may
222 * now be unset.
223 */
224 td = curthread;
225 if (td->td_critnest != 0)
226 return;
227 if (kdb_active)
228 return;
229
230 /*
231 * Microoptimization: we committed to switch,
232 * disable preemption in interrupt handlers
233 * while spinning for the thread lock.
234 */
235 td->td_critnest = 1;
236 thread_lock(td);
237 td->td_critnest--;
238 flags = SW_INVOL | SW_PREEMPT;
239 if (TD_IS_IDLETHREAD(td))
240 flags |= SWT_IDLE;
241 else
242 flags |= SWT_OWEPREEMPT;
243 mi_switch(flags);
244 }
245
246 void
critical_exit_KBI(void)247 critical_exit_KBI(void)
248 {
249 #ifdef KTR
250 struct thread *td = curthread;
251 #endif
252 critical_exit();
253 CTR4(KTR_CRITICAL, "critical_exit by thread %p (%ld, %s) to %d", td,
254 (long)td->td_proc->p_pid, td->td_name, td->td_critnest);
255 }
256
257 /************************************************************************
258 * SYSTEM RUN QUEUE manipulations and tests *
259 ************************************************************************/
260 /*
261 * Initialize a run structure.
262 */
263 void
runq_init(struct runq * rq)264 runq_init(struct runq *rq)
265 {
266 int i;
267
268 bzero(rq, sizeof *rq);
269 for (i = 0; i < RQ_NQS; i++)
270 TAILQ_INIT(&rq->rq_queues[i]);
271 }
272
273 /*
274 * Clear the status bit of the queue corresponding to priority level pri,
275 * indicating that it is empty.
276 */
277 static __inline void
runq_clrbit(struct runq * rq,int pri)278 runq_clrbit(struct runq *rq, int pri)
279 {
280 struct rqbits *rqb;
281
282 rqb = &rq->rq_status;
283 CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
284 rqb->rqb_bits[RQB_WORD(pri)],
285 rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
286 RQB_BIT(pri), RQB_WORD(pri));
287 rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
288 }
289
290 /*
291 * Find the index of the first non-empty run queue. This is done by
292 * scanning the status bits, a set bit indicates a non-empty queue.
293 */
294 static __inline int
runq_findbit(struct runq * rq)295 runq_findbit(struct runq *rq)
296 {
297 struct rqbits *rqb;
298 int pri;
299 int i;
300
301 rqb = &rq->rq_status;
302 for (i = 0; i < RQB_LEN; i++)
303 if (rqb->rqb_bits[i]) {
304 pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW);
305 CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
306 rqb->rqb_bits[i], i, pri);
307 return (pri);
308 }
309
310 return (-1);
311 }
312
313 static __inline int
runq_findbit_from(struct runq * rq,u_char pri)314 runq_findbit_from(struct runq *rq, u_char pri)
315 {
316 struct rqbits *rqb;
317 rqb_word_t mask;
318 int i;
319
320 /*
321 * Set the mask for the first word so we ignore priorities before 'pri'.
322 */
323 mask = (rqb_word_t)-1 << (pri & (RQB_BPW - 1));
324 rqb = &rq->rq_status;
325 again:
326 for (i = RQB_WORD(pri); i < RQB_LEN; mask = -1, i++) {
327 mask = rqb->rqb_bits[i] & mask;
328 if (mask == 0)
329 continue;
330 pri = RQB_FFS(mask) + (i << RQB_L2BPW);
331 CTR3(KTR_RUNQ, "runq_findbit_from: bits=%#x i=%d pri=%d",
332 mask, i, pri);
333 return (pri);
334 }
335 if (pri == 0)
336 return (-1);
337 /*
338 * Wrap back around to the beginning of the list just once so we
339 * scan the whole thing.
340 */
341 pri = 0;
342 goto again;
343 }
344
345 /*
346 * Set the status bit of the queue corresponding to priority level pri,
347 * indicating that it is non-empty.
348 */
349 static __inline void
runq_setbit(struct runq * rq,int pri)350 runq_setbit(struct runq *rq, int pri)
351 {
352 struct rqbits *rqb;
353
354 rqb = &rq->rq_status;
355 CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
356 rqb->rqb_bits[RQB_WORD(pri)],
357 rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
358 RQB_BIT(pri), RQB_WORD(pri));
359 rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
360 }
361
362 /*
363 * Add the thread to the queue specified by its priority, and set the
364 * corresponding status bit.
365 */
366 void
runq_add(struct runq * rq,struct thread * td,int flags)367 runq_add(struct runq *rq, struct thread *td, int flags)
368 {
369 struct rqhead *rqh;
370 int pri;
371
372 pri = td->td_priority / RQ_PPQ;
373 td->td_rqindex = pri;
374 runq_setbit(rq, pri);
375 rqh = &rq->rq_queues[pri];
376 CTR4(KTR_RUNQ, "runq_add: td=%p pri=%d %d rqh=%p",
377 td, td->td_priority, pri, rqh);
378 if (flags & SRQ_PREEMPTED) {
379 TAILQ_INSERT_HEAD(rqh, td, td_runq);
380 } else {
381 TAILQ_INSERT_TAIL(rqh, td, td_runq);
382 }
383 }
384
385 void
runq_add_pri(struct runq * rq,struct thread * td,u_char pri,int flags)386 runq_add_pri(struct runq *rq, struct thread *td, u_char pri, int flags)
387 {
388 struct rqhead *rqh;
389
390 KASSERT(pri < RQ_NQS, ("runq_add_pri: %d out of range", pri));
391 td->td_rqindex = pri;
392 runq_setbit(rq, pri);
393 rqh = &rq->rq_queues[pri];
394 CTR4(KTR_RUNQ, "runq_add_pri: td=%p pri=%d idx=%d rqh=%p",
395 td, td->td_priority, pri, rqh);
396 if (flags & SRQ_PREEMPTED) {
397 TAILQ_INSERT_HEAD(rqh, td, td_runq);
398 } else {
399 TAILQ_INSERT_TAIL(rqh, td, td_runq);
400 }
401 }
402 /*
403 * Return true if there are runnable processes of any priority on the run
404 * queue, false otherwise. Has no side effects, does not modify the run
405 * queue structure.
406 */
407 int
runq_check(struct runq * rq)408 runq_check(struct runq *rq)
409 {
410 struct rqbits *rqb;
411 int i;
412
413 rqb = &rq->rq_status;
414 for (i = 0; i < RQB_LEN; i++)
415 if (rqb->rqb_bits[i]) {
416 CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
417 rqb->rqb_bits[i], i);
418 return (1);
419 }
420 CTR0(KTR_RUNQ, "runq_check: empty");
421
422 return (0);
423 }
424
425 /*
426 * Find the highest priority process on the run queue.
427 */
428 struct thread *
runq_choose_fuzz(struct runq * rq,int fuzz)429 runq_choose_fuzz(struct runq *rq, int fuzz)
430 {
431 struct rqhead *rqh;
432 struct thread *td;
433 int pri;
434
435 while ((pri = runq_findbit(rq)) != -1) {
436 rqh = &rq->rq_queues[pri];
437 /* fuzz == 1 is normal.. 0 or less are ignored */
438 if (fuzz > 1) {
439 /*
440 * In the first couple of entries, check if
441 * there is one for our CPU as a preference.
442 */
443 int count = fuzz;
444 int cpu = PCPU_GET(cpuid);
445 struct thread *td2;
446 td2 = td = TAILQ_FIRST(rqh);
447
448 while (count-- && td2) {
449 if (td2->td_lastcpu == cpu) {
450 td = td2;
451 break;
452 }
453 td2 = TAILQ_NEXT(td2, td_runq);
454 }
455 } else
456 td = TAILQ_FIRST(rqh);
457 KASSERT(td != NULL, ("runq_choose_fuzz: no proc on busy queue"));
458 CTR3(KTR_RUNQ,
459 "runq_choose_fuzz: pri=%d thread=%p rqh=%p", pri, td, rqh);
460 return (td);
461 }
462 CTR1(KTR_RUNQ, "runq_choose_fuzz: idleproc pri=%d", pri);
463
464 return (NULL);
465 }
466
467 /*
468 * Find the highest priority process on the run queue.
469 */
470 struct thread *
runq_choose(struct runq * rq)471 runq_choose(struct runq *rq)
472 {
473 struct rqhead *rqh;
474 struct thread *td;
475 int pri;
476
477 while ((pri = runq_findbit(rq)) != -1) {
478 rqh = &rq->rq_queues[pri];
479 td = TAILQ_FIRST(rqh);
480 KASSERT(td != NULL, ("runq_choose: no thread on busy queue"));
481 CTR3(KTR_RUNQ,
482 "runq_choose: pri=%d thread=%p rqh=%p", pri, td, rqh);
483 return (td);
484 }
485 CTR1(KTR_RUNQ, "runq_choose: idlethread pri=%d", pri);
486
487 return (NULL);
488 }
489
490 struct thread *
runq_choose_from(struct runq * rq,u_char idx)491 runq_choose_from(struct runq *rq, u_char idx)
492 {
493 struct rqhead *rqh;
494 struct thread *td;
495 int pri;
496
497 if ((pri = runq_findbit_from(rq, idx)) != -1) {
498 rqh = &rq->rq_queues[pri];
499 td = TAILQ_FIRST(rqh);
500 KASSERT(td != NULL, ("runq_choose: no thread on busy queue"));
501 CTR4(KTR_RUNQ,
502 "runq_choose_from: pri=%d thread=%p idx=%d rqh=%p",
503 pri, td, td->td_rqindex, rqh);
504 return (td);
505 }
506 CTR1(KTR_RUNQ, "runq_choose_from: idlethread pri=%d", pri);
507
508 return (NULL);
509 }
510 /*
511 * Remove the thread from the queue specified by its priority, and clear the
512 * corresponding status bit if the queue becomes empty.
513 * Caller must set state afterwards.
514 */
515 void
runq_remove(struct runq * rq,struct thread * td)516 runq_remove(struct runq *rq, struct thread *td)
517 {
518
519 runq_remove_idx(rq, td, NULL);
520 }
521
522 void
runq_remove_idx(struct runq * rq,struct thread * td,u_char * idx)523 runq_remove_idx(struct runq *rq, struct thread *td, u_char *idx)
524 {
525 struct rqhead *rqh;
526 u_char pri;
527
528 KASSERT(td->td_flags & TDF_INMEM,
529 ("runq_remove_idx: thread swapped out"));
530 pri = td->td_rqindex;
531 KASSERT(pri < RQ_NQS, ("runq_remove_idx: Invalid index %d\n", pri));
532 rqh = &rq->rq_queues[pri];
533 CTR4(KTR_RUNQ, "runq_remove_idx: td=%p, pri=%d %d rqh=%p",
534 td, td->td_priority, pri, rqh);
535 TAILQ_REMOVE(rqh, td, td_runq);
536 if (TAILQ_EMPTY(rqh)) {
537 CTR0(KTR_RUNQ, "runq_remove_idx: empty");
538 runq_clrbit(rq, pri);
539 if (idx != NULL && *idx == pri)
540 *idx = (pri + 1) % RQ_NQS;
541 }
542 }
543