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 #ifdef INVARIANT_SUPPORT
 156 /*
 157  * Return true if the specified process is already in the run queue.
 158  */
 159 static __inline int
 160 runq_find(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         KASSERT(runq_find(rq, ke) == 0,
 193             ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm));
 194         pri = ke->ke_thread->td_priority / RQ_PPQ;
 195         ke->ke_rqindex = pri;
 196         runq_setbit(rq, pri);
 197         rqh = &rq->rq_queues[pri];
 198         CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
 199             ke->ke_proc, ke->ke_thread->td_priority, pri, rqh);
 200         TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
 201         ke->ke_flags |= KEF_ONRUNQ;
 202 }
 203
 204 /*
 205  * Return true if there are runnable processes of any priority on the run
 206  * queue, false otherwise.  Has no side effects, does not modify the run
 207  * queue structure.
 208  */
 209 int
 210 runq_check(struct runq *rq)
 211 {
 212         struct rqbits *rqb;
 213         int i;
 214
 215         rqb = &rq->rq_status;
 216         for (i = 0; i < RQB_LEN; i++)
 217                 if (rqb->rqb_bits[i]) {
 218                         CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
 219                             rqb->rqb_bits[i], i);
 220                         return (1);
 221                 }
 222         CTR0(KTR_RUNQ, "runq_check: empty");
 223
 224         return (0);
 225 }
 226
 227 /*
 228  * Find and remove the highest priority process from the run queue.
 229  * If there are no runnable processes, the per-cpu idle process is
 230  * returned.  Will not return NULL under any circumstances.
 231  */
 232 struct kse *
 233 runq_choose(struct runq *rq)
 234 {
 235         struct rqhead *rqh;
 236         struct kse *ke;
 237         int pri;
 238
 239         mtx_assert(&sched_lock, MA_OWNED);
 240         if ((pri = runq_findbit(rq)) != -1) {
 241                 rqh = &rq->rq_queues[pri];
 242                 ke = TAILQ_FIRST(rqh);
 243                 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
 244                 KASSERT(ke->ke_proc->p_stat == SRUN,
 245                     ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid,
 246                     ke->ke_proc->p_comm, ke->ke_proc->p_stat));
 247                 CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
 248                 TAILQ_REMOVE(rqh, ke, ke_procq);
 249                 if (TAILQ_EMPTY(rqh)) {
 250                         CTR0(KTR_RUNQ, "runq_choose: empty");
 251                         runq_clrbit(rq, pri);
 252                 }
 253                 ke->ke_flags &= ~KEF_ONRUNQ;
 254                 return (ke);
 255         }
 256         CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
 257
 258         return (PCPU_GET(idlethread)->td_kse);
 259 }
 260
 261 /*
 262  * Initialize a run structure.
 263  */
 264 void
 265 runq_init(struct runq *rq)
 266 {
 267         int i;
 268
 269         bzero(rq, sizeof *rq);
 270         for (i = 0; i < RQ_NQS; i++)
 271                 TAILQ_INIT(&rq->rq_queues[i]);
 272 }
 273
 274 /*
 275  * Remove the process from the queue specified by its priority, and clear the
 276  * corresponding status bit if the queue becomes empty.
 277  */
 278 void
 279 runq_remove(struct runq *rq, struct kse *ke)
 280 {
 281         struct rqhead *rqh;
 282         int pri;
 283
 284         if (!(ke->ke_flags & KEF_ONRUNQ))
 285                 return;
 286         mtx_assert(&sched_lock, MA_OWNED);
 287         pri = ke->ke_rqindex;
 288         rqh = &rq->rq_queues[pri];
 289         CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
 290             ke, ke->ke_thread->td_priority, pri, rqh);
 291         KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
 292         TAILQ_REMOVE(rqh, ke, ke_procq);
 293         if (TAILQ_EMPTY(rqh)) {
 294                 CTR0(KTR_RUNQ, "runq_remove: empty");
 295                 runq_clrbit(rq, pri);
 296         }
 297         ke->ke_flags &= ~KEF_ONRUNQ;
 298 }