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