sys/kern/kern_switch.c

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