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 #include <machine/critical.h>
  38
  39 /*
  40  * Global run queue.
  41  */
  42 static struct runq runq;
  43 SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq)
  44
  45 /*
  46  * Wrappers which implement old interface; act on global run queue.
  47  */
  48
  49 struct thread *
  50 choosethread(void)
  51 {
  52         return (runq_choose(&runq)->ke_thread);
  53 }
  54
  55 int
  56 procrunnable(void)
  57 {
  58         return runq_check(&runq);
  59 }
  60
  61 void
  62 remrunqueue(struct thread *td)
  63 {
  64         runq_remove(&runq, td->td_kse);
  65 }
  66
  67 void
  68 setrunqueue(struct thread *td)
  69 {
  70         runq_add(&runq, td->td_kse);
  71 }
  72
  73 /* Critical sections that prevent preemption. */
  74 void
  75 critical_enter(void)
  76 {
  77         struct thread *td;
  78
  79         td = curthread;
  80         if (td->td_critnest == 0)
  81                 cpu_critical_enter();
  82         td->td_critnest++;
  83 }
  84
  85 void
  86 critical_exit(void)
  87 {
  88         struct thread *td;
  89
  90         td = curthread;
  91         if (td->td_critnest == 1) {
  92                 td->td_critnest = 0;
  93                 cpu_critical_exit();
  94         } else {
  95                 td->td_critnest--;
  96         }
  97 }
  98
  99 /*
 100  * Clear the status bit of the queue corresponding to priority level pri,
 101  * indicating that it is empty.
 102  */
 103 static __inline void
 104 runq_clrbit(struct runq *rq, int pri)
 105 {
 106         struct rqbits *rqb;
 107
 108         rqb = &rq->rq_status;
 109         CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
 110             rqb->rqb_bits[RQB_WORD(pri)],
 111             rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
 112             RQB_BIT(pri), RQB_WORD(pri));
 113         rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
 114 }
 115
 116 /*
 117  * Find the index of the first non-empty run queue.  This is done by
 118  * scanning the status bits, a set bit indicates a non-empty queue.
 119  */
 120 static __inline int
 121 runq_findbit(struct runq *rq)
 122 {
 123         struct rqbits *rqb;
 124         int pri;
 125         int i;
 126
 127         rqb = &rq->rq_status;
 128         for (i = 0; i < RQB_LEN; i++)
 129                 if (rqb->rqb_bits[i]) {
 130                         pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) +
 131                             (i << RQB_L2BPW);
 132                         CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
 133                             rqb->rqb_bits[i], i, pri);
 134                         return (pri);
 135                 }
 136
 137         return (-1);
 138 }
 139
 140 /*
 141  * Set the status bit of the queue corresponding to priority level pri,
 142  * indicating that it is non-empty.
 143  */
 144 static __inline void
 145 runq_setbit(struct runq *rq, int pri)
 146 {
 147         struct rqbits *rqb;
 148
 149         rqb = &rq->rq_status;
 150         CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
 151             rqb->rqb_bits[RQB_WORD(pri)],
 152             rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
 153             RQB_BIT(pri), RQB_WORD(pri));
 154         rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
 155 }
 156
 157 #if defined(INVARIANT_SUPPORT) && defined(DIAGNOSTIC)
 158 /*
 159  * Return true if the specified process is already in the run queue.
 160  */
 161 static __inline int
 162 runq_findproc(struct runq *rq, struct kse *ke)
 163 {
 164         struct kse *ke2;
 165         int i;
 166
 167         mtx_assert(&sched_lock, MA_OWNED);
 168         for (i = 0; i < RQB_LEN; i++)
 169                 TAILQ_FOREACH(ke2, &rq->rq_queues[i], ke_procq)
 170                     if (ke2 == ke)
 171                             return 1;
 172         return 0;
 173 }
 174 #endif
 175
 176 /*
 177  * Add the process to the queue specified by its priority, and set the
 178  * corresponding status bit.
 179  */
 180 void
 181 runq_add(struct runq *rq, struct kse *ke)
 182 {
 183         struct rqhead *rqh;
 184         int pri;
 185
 186 #ifdef INVARIANTS
 187         struct proc *p = ke->ke_proc;
 188 #endif
 189         if (ke->ke_flags & KEF_ONRUNQ)
 190                 return;
 191         mtx_assert(&sched_lock, MA_OWNED);
 192         KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN",
 193             p, p->p_comm));
 194 #if defined(INVARIANTS) && defined(DIAGNOSTIC)
 195         KASSERT(runq_findproc(rq, ke) == 0,
 196             ("runq_add: proc %p (%s) already in run queue", ke, p->p_comm));
 197 #endif
 198         pri = ke->ke_thread->td_priority / RQ_PPQ;
 199         ke->ke_rqindex = pri;
 200         runq_setbit(rq, pri);
 201         rqh = &rq->rq_queues[pri];
 202         CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
 203             ke->ke_proc, ke->ke_thread->td_priority, pri, rqh);
 204         TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
 205         ke->ke_flags |= KEF_ONRUNQ;
 206 }
 207
 208 /*
 209  * Return true if there are runnable processes of any priority on the run
 210  * queue, false otherwise.  Has no side effects, does not modify the run
 211  * queue structure.
 212  */
 213 int
 214 runq_check(struct runq *rq)
 215 {
 216         struct rqbits *rqb;
 217         int i;
 218
 219         rqb = &rq->rq_status;
 220         for (i = 0; i < RQB_LEN; i++)
 221                 if (rqb->rqb_bits[i]) {
 222                         CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
 223                             rqb->rqb_bits[i], i);
 224                         return (1);
 225                 }
 226         CTR0(KTR_RUNQ, "runq_check: empty");
 227
 228         return (0);
 229 }
 230
 231 /*
 232  * Find and remove the highest priority process from the run queue.
 233  * If there are no runnable processes, the per-cpu idle process is
 234  * returned.  Will not return NULL under any circumstances.
 235  */
 236 struct kse *
 237 runq_choose(struct runq *rq)
 238 {
 239         struct rqhead *rqh;
 240         struct kse *ke;
 241         int pri;
 242
 243         mtx_assert(&sched_lock, MA_OWNED);
 244         if ((pri = runq_findbit(rq)) != -1) {
 245                 rqh = &rq->rq_queues[pri];
 246                 ke = TAILQ_FIRST(rqh);
 247                 KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
 248                 KASSERT(ke->ke_proc->p_stat == SRUN,
 249                     ("runq_choose: process %d(%s) in state %d", ke->ke_proc->p_pid,
 250                     ke->ke_proc->p_comm, ke->ke_proc->p_stat));
 251                 CTR3(KTR_RUNQ, "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
 252                 TAILQ_REMOVE(rqh, ke, ke_procq);
 253                 if (TAILQ_EMPTY(rqh)) {
 254                         CTR0(KTR_RUNQ, "runq_choose: empty");
 255                         runq_clrbit(rq, pri);
 256                 }
 257                 ke->ke_flags &= ~KEF_ONRUNQ;
 258                 return (ke);
 259         }
 260         CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
 261
 262         return (PCPU_GET(idlethread)->td_kse);
 263 }
 264
 265 /*
 266  * Initialize a run structure.
 267  */
 268 void
 269 runq_init(struct runq *rq)
 270 {
 271         int i;
 272
 273         bzero(rq, sizeof *rq);
 274         for (i = 0; i < RQ_NQS; i++)
 275                 TAILQ_INIT(&rq->rq_queues[i]);
 276 }
 277
 278 /*
 279  * Remove the process from the queue specified by its priority, and clear the
 280  * corresponding status bit if the queue becomes empty.
 281  */
 282 void
 283 runq_remove(struct runq *rq, struct kse *ke)
 284 {
 285         struct rqhead *rqh;
 286         int pri;
 287
 288         if (!(ke->ke_flags & KEF_ONRUNQ))
 289                 return;
 290         mtx_assert(&sched_lock, MA_OWNED);
 291         pri = ke->ke_rqindex;
 292         rqh = &rq->rq_queues[pri];
 293         CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
 294             ke, ke->ke_thread->td_priority, pri, rqh);
 295         KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
 296         TAILQ_REMOVE(rqh, ke, ke_procq);
 297         if (TAILQ_EMPTY(rqh)) {
 298                 CTR0(KTR_RUNQ, "runq_remove: empty");
 299                 runq_clrbit(rq, pri);
 300         }
 301         ke->ke_flags &= ~KEF_ONRUNQ;
 302 }