sys/kern/kern_switch.c

   1 /*
   2  * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $FreeBSD$
  27  */
  28
  29 #include <sys/param.h>
  30 #include <sys/systm.h>
  31 #include <sys/kernel.h>
  32 #include <sys/ktr.h>
  33 #include <sys/lock.h>
  34 #include <sys/mutex.h>
  35 #include <sys/proc.h>
  36 #include <sys/queue.h>
  37
  38 /*
  39  * Global run queue.
  40  */
  41 static struct runq runq;
  42 SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq)
  43
  44 /*
  45  * Wrappers which implement old interface; act on global run queue.
  46  */
  47
  48 struct thread *
  49 choosethread(void)
  50 {
  51         return (runq_choose(&runq)->ke_thread);
  52 }
  53
  54 int
  55 procrunnable(void)
  56 {
  57         return runq_check(&runq);
  58 }
  59
  60 void
  61 remrunqueue(struct thread *td)
  62 {
  63         runq_remove(&runq, td->td_kse);
  64 }
  65
  66 void
  67 setrunqueue(struct thread *td)
  68 {
  69         runq_add(&runq, td->td_kse);
  70 }
  71
  72 /* Critical sections that prevent preemption. */
  73 void
  74 critical_enter(void)
  75 {
  76         struct thread *td;
  77
  78         td = curthread;
  79         if (td->td_critnest == 0)
  80                 td->td_savecrit = cpu_critical_enter();
  81         td->td_critnest++;
  82 }
  83
  84 void
  85 critical_exit(void)
  86 {
  87         struct thread *td;
  88
  89         td = curthread;
  90         if (td->td_critnest == 1) {
  91                 td->td_critnest = 0;
  92                 cpu_critical_exit(td->td_savecrit);
  93         } else
  94                 td->td_critnest--;
  95 }
  96
  97 /*
  98  * Clear the status bit of the queue corresponding to priority level pri,
  99  * indicating that it is empty.
 100  */
 101 static __inline void
 102 runq_clrbit(struct runq *rq, int pri)
 103 {
 104         struct rqbits *rqb;
 105
 106         rqb = &rq->rq_status;
 107         CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
 108             rqb->rqb_bits[RQB_WORD(pri)],
 109             rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
 110             RQB_BIT(pri), RQB_WORD(pri));
 111         rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
 112 }
 113
 114 /*
 115  * Find the index of the first non-empty run queue.  This is done by
 116  * scanning the status bits, a set bit indicates a non-empty queue.
 117  */
 118 static __inline int
 119 runq_findbit(struct runq *rq)
 120 {
 121         struct rqbits *rqb;
 122         int pri;
 123         int i;
 124
 125         rqb = &rq->rq_status;
 126         for (i = 0; i < RQB_LEN; i++)
 127                 if (rqb->rqb_bits[i]) {
 128                         pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) +
 129                             (i << RQB_L2BPW);
 130                         CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
 131                             rqb->rqb_bits[i], i, pri);
 132                         return (pri);
 133                 }
 134
 135         return (-1);
 136 }
 137
 138 /*
 139  * Set the status bit of the queue corresponding to priority level pri,
 140  * indicating that it is non-empty.
 141  */
 142 static __inline void
 143 runq_setbit(struct runq *rq, int pri)
 144 {
 145         struct rqbits *rqb;
 146
 147         rqb = &rq->rq_status;
 148         CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
 149             rqb->rqb_bits[RQB_WORD(pri)],
 150             rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
 151             RQB_BIT(pri), RQB_WORD(pri));
 152         rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
 153 }
 154
 155 #if defined(INVARIANT_SUPPORT) && defined(DIAGNOSTIC)
 156 /*
 157  * Return true if the specified process is already in the run queue.
 158  */
 159 static __inline int
 160 runq_findproc(struct runq *rq, struct kse *ke)
 161 {
 162         struct kse *ke2;
 163         int i;
 164
 165         mtx_assert(&sched_lock, MA_OWNED);
 166         for (i = 0; i < RQB_LEN; i++)
 167                 TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq)
 168                     if (ke2 == ke)
 169                             return 1;
 170         return 0;
 171 }
 172 #endif
 173
 174 /*
 175  * Add the process to the queue specified by its priority, and set the
 176  * corresponding status bit.
 177  */
 178 void
 179 runq_add(struct runq *rq, struct kse *ke)
 180 {
 181         struct rqhead *rqh;
 182         int pri;
 183
 184 #ifdef INVARIANTS
 185         struct proc *p = ke->ke_proc;
 186 #endif
 187         if (ke->ke_flags & KEF_ONRUNQ)
 188                 return;
 189         mtx_assert(&sched_lock, MA_OWNED);
 190         KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN",
 191             p, p->p_comm));
 192 #if defined(INVARIANTS) && defined(DIAGNOSTIC)
 193         KASSERT(runq_findproc(rq, ke) == 0,
 194             ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm));
 195 #endif
 196         pri = ke->ke_thread->td_priority / RQ_PPQ;
 197         ke->ke_rqindex = pri;
 198         runq_setbit(rq, pri);
 199         rqh = &rq->rq_queues[pri];
 200         CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
 201             ke->ke_proc, ke->ke_thread->td_priority, pri, rqh);
 202         TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
 203         ke->ke_flags |= KEF_ONRUNQ;
 204 }
 205
 206 /*
 207  * Return true if there are runnable processes of any priority on the run
 208  * queue, false otherwise.  Has no side effects, does not modify the run
 209  * queue structure.
 210  */
 211 int
 212 runq_check(struct runq *rq)
 213 {
 214         struct rqbits *rqb;
 215         int i;
 216
 217         rqb = &rq->rq_status;
 218         for (i = 0; i < RQB_LEN; i++)
 219                 if (rqb->rqb_bits[i]) {
 220                         CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
 221                             rqb->rqb_bits[i], i);
 222                         return (1);
 223                 }
 224         CTR0(KTR_RUNQ, "runq_check: empty");
 225
 226         return (0);
 227 }
 228
 229 /*
 230  * Find and remove the highest priority process from the run queue.
 231  * If there are no runnable processes, the per-cpu idle process is
 232  * returned.  Will not return NULL under any circumstances.
 233  */
 234 struct kse *
 235 runq_choose(struct runq *rq)
 236 {
 237         struct rqhead *rqh;
 238         struct kse *ke;
 239         int pri;
 240
 241         mtx_assert(&sched_lock, MA_OWNED);
 242         if ((pri = runq_findbit(rq)) != -1) {
 243                 rqh = &rq->rq_queues[pri];
 244                 ke = TAILQ_FIRST(rqh);
 245                 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
 246                 KASSERT(ke->ke_proc->p_stat == SRUN,
 247                     ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid,
 248                     ke->ke_proc->p_comm, ke->ke_proc->p_stat));
 249                 CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
 250                 TAILQ_REMOVE(rqh, ke, ke_procq);
 251                 if (TAILQ_EMPTY(rqh)) {
 252                         CTR0(KTR_RUNQ, "runq_choose: empty");
 253                         runq_clrbit(rq, pri);
 254                 }
 255                 ke->ke_flags &= ~KEF_ONRUNQ;
 256                 return (ke);
 257         }
 258         CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
 259
 260         return (PCPU_GET(idlethread)->td_kse);
 261 }
 262
 263 /*
 264  * Initialize a run structure.
 265  */
 266 void
 267 runq_init(struct runq *rq)
 268 {
 269         int i;
 270
 271         bzero(rq, sizeof *rq);
 272         for (i = 0; i < RQ_NQS; i++)
 273                 TAILQ_INIT(&rq->rq_queues[i]);
 274 }
 275
 276 /*
 277  * Remove the process from the queue specified by its priority, and clear the
 278  * corresponding status bit if the queue becomes empty.
 279  */
 280 void
 281 runq_remove(struct runq *rq, struct kse *ke)
 282 {
 283         struct rqhead *rqh;
 284         int pri;
 285
 286         if (!(ke->ke_flags & KEF_ONRUNQ))
 287                 return;
 288         mtx_assert(&sched_lock, MA_OWNED);
 289         pri = ke->ke_rqindex;
 290         rqh = &rq->rq_queues[pri];
 291         CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
 292             ke, ke->ke_thread->td_priority, pri, rqh);
 293         KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
 294         TAILQ_REMOVE(rqh, ke, ke_procq);
 295         if (TAILQ_EMPTY(rqh)) {
 296                 CTR0(KTR_RUNQ, "runq_remove: empty");
 297                 runq_clrbit(rq, pri);
 298         }
 299         ke->ke_flags &= ~KEF_ONRUNQ;
 300 }