sys/kern/kern_switch.c

   1 /*
   2  * Copyright (c) 1999 Peter Wemm <peter@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: src/sys/kern/kern_switch.c,v 1.3.2.1 2000/05/16 06:58:12 dillon Exp $
  27  * $DragonFly: src/sys/kern/Attic/kern_switch.c,v 1.10 2003/10/16 22:26:37 dillon Exp $
  28  */
  29
  30 #include <sys/param.h>
  31 #include <sys/systm.h>
  32 #include <sys/kernel.h>
  33 #include <sys/lock.h>
  34 #include <sys/queue.h>
  35 #include <sys/proc.h>
  36 #include <sys/rtprio.h>
  37 #include <sys/thread2.h>
  38 #include <sys/uio.h>
  39 #include <sys/sysctl.h>
  40 #include <machine/ipl.h>
  41 #include <machine/cpu.h>
  42
  43 /*
  44  * debugging only YYY Remove me!   define to schedule user processes only
  45  * on the BSP.  Interrupts can still be taken on the APs.
  46  */
  47 #undef ONLY_ONE_USER_CPU
  48
  49 /*
  50  * We have NQS (32) run queues per scheduling class.  For the normal
  51  * class, there are 128 priorities scaled onto these 32 queues.  New
  52  * processes are added to the last entry in each queue, and processes
  53  * are selected for running by taking them from the head and maintaining
  54  * a simple FIFO arrangement.  Realtime and Idle priority processes have
  55  * and explicit 0-31 priority which maps directly onto their class queue
  56  * index.  When a queue has something in it, the corresponding bit is
  57  * set in the queuebits variable, allowing a single read to determine
  58  * the state of all 32 queues and then a ffs() to find the first busy
  59  * queue.
  60  */
  61 static struct rq queues[NQS];
  62 static struct rq rtqueues[NQS];
  63 static struct rq idqueues[NQS];
  64 static u_int32_t queuebits;
  65 static u_int32_t rtqueuebits;
  66 static u_int32_t idqueuebits;
  67 static u_int32_t curprocmask = -1;      /* currently running a user process */
  68 static u_int32_t rdyprocmask;           /* ready to accept a user process */
  69 static int       runqcount;
  70
  71 SYSCTL_INT(_debug, OID_AUTO, runqcount, CTLFLAG_RD, &runqcount, 0, "");
  72 static int usched_steal;
  73 SYSCTL_INT(_debug, OID_AUTO, usched_steal, CTLFLAG_RW,
  74         &usched_steal, 0, "Passive Release was nonoptimal");
  75 static int usched_optimal;
  76 SYSCTL_INT(_debug, OID_AUTO, usched_optimal, CTLFLAG_RW,
  77         &usched_optimal, 0, "Passive Release was nonoptimal");
  78
  79 #define USCHED_COUNTER(td)      ((td->td_gd == mycpu) ? ++usched_optimal : ++usched_steal)
  80
  81 /*
  82  * Initialize the run queues at boot time.
  83  */
  84 static void
  85 rqinit(void *dummy)
  86 {
  87         int i;
  88
  89         for (i = 0; i < NQS; i++) {
  90                 TAILQ_INIT(&queues[i]);
  91                 TAILQ_INIT(&rtqueues[i]);
  92                 TAILQ_INIT(&idqueues[i]);
  93         }
  94 #ifdef SMP
  95         sched_thread_init();
  96 #else
  97         curprocmask &= ~1;
  98 #endif
  99 }
 100 SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL)
 101
 102 static int
 103 test_resched(struct proc *curp, struct proc *newp)
 104 {
 105         if (newp->p_rtprio.type < curp->p_rtprio.type)
 106                 return(1);
 107         if (newp->p_rtprio.type == curp->p_rtprio.type) {
 108                 if (newp->p_rtprio.type == RTP_PRIO_NORMAL) {
 109                         if (newp->p_priority / PPQ <= curp->p_priority / PPQ)
 110                                 return(1);
 111                 } else if (newp->p_rtprio.prio < curp->p_rtprio.prio) {
 112                         return(1);
 113                 }
 114         }
 115         return(0);
 116 }
 117
 118 /*
 119  * chooseproc() is called when a cpu needs a user process to LWKT schedule.
 120  * chooseproc() will select a user process and return it.
 121  */
 122 static
 123 struct proc *
 124 chooseproc(void)
 125 {
 126         struct proc *p;
 127         struct rq *q;
 128         u_int32_t *which;
 129         u_int32_t pri;
 130
 131         if (rtqueuebits) {
 132                 pri = bsfl(rtqueuebits);
 133                 q = &rtqueues[pri];
 134                 which = &rtqueuebits;
 135         } else if (queuebits) {
 136                 pri = bsfl(queuebits);
 137                 q = &queues[pri];
 138                 which = &queuebits;
 139         } else if (idqueuebits) {
 140                 pri = bsfl(idqueuebits);
 141                 q = &idqueues[pri];
 142                 which = &idqueuebits;
 143         } else {
 144                 return NULL;
 145         }
 146         p = TAILQ_FIRST(q);
 147         KASSERT(p, ("chooseproc: no proc on busy queue"));
 148         TAILQ_REMOVE(q, p, p_procq);
 149         --runqcount;
 150         if (TAILQ_EMPTY(q))
 151                 *which &= ~(1 << pri);
 152         KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq6!"));
 153         p->p_flag &= ~P_ONRUNQ;
 154         return p;
 155 }
 156
 157
 158 /*
 159  * setrunqueue() 'wakes up' a 'user' process, which can mean several things.
 160  *
 161  * If P_CP_RELEASED is set the user process is under the control of the
 162  * LWKT subsystem and we simply wake the thread up.  This is ALWAYS the
 163  * case when setrunqueue() is called from wakeup() and, in fact wakeup()
 164  * asserts that P_CP_RELEASED is set.
 165  *
 166  * Note that acquire_curproc() already optimizes making the current process
 167  * P_CURPROC, so setrunqueue() does not need to.
 168  *
 169  * If P_CP_RELEASED is not set we place the process on the run queue and we
 170  * signal other cpus in the system that may need to be woken up to service
 171  * the new 'user' process.
 172  *
 173  * If P_PASSIVE_ACQ is set setrunqueue() will not wakeup potential target
 174  * cpus in an attempt to keep the process on the current cpu at least for
 175  * a little while to take advantage of locality of reference (e.g. fork/exec
 176  * or short fork/exit).
 177  *
 178  * WARNING! a thread can be acquired by another cpu the moment it is put
 179  * on the user scheduler's run queue AND we release the MP lock.  Since we
 180  * release the MP lock before switching out another cpu may begin stealing
 181  * our current thread before we are completely switched out!  The
 182  * lwkt_acquire() function will stall until TDF_RUNNING is cleared on the
 183  * thread before stealing it.
 184  *
 185  * The associated thread must NOT be scheduled.
 186  * The process must be runnable.
 187  * This must be called at splhigh().
 188  */
 189 void
 190 setrunqueue(struct proc *p)
 191 {
 192         struct rq *q;
 193         int pri;
 194         int cpuid;
 195         u_int32_t mask;
 196
 197         crit_enter();
 198         KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));
 199         KASSERT((p->p_flag & (P_ONRUNQ|P_CURPROC)) == 0,
 200             ("process %d already on runq! flag %08x", p->p_pid, p->p_flag));
 201         KKASSERT((p->p_thread->td_flags & TDF_RUNQ) == 0);
 202
 203         /*
 204          * If we have been released from the userland scheduler we
 205          * directly schedule its thread.
 206          */
 207         if (p->p_flag & P_CP_RELEASED) {
 208                 lwkt_schedule(p->p_thread);
 209                 crit_exit();
 210                 return;
 211         }
 212
 213         /*
 214          * If our cpu is available to run a user process we short cut and
 215          * just do it.
 216          */
 217         cpuid = mycpu->gd_cpuid;
 218         if ((curprocmask & (1 << cpuid)) == 0) {
 219                 curprocmask |= 1 << cpuid;
 220                 p->p_flag |= P_CURPROC;
 221                 USCHED_COUNTER(p->p_thread);
 222                 lwkt_acquire(p->p_thread);
 223                 lwkt_schedule(p->p_thread);
 224                 crit_exit();
 225                 return;
 226         }
 227
 228         /*
 229          * Otherwise place this process on the userland scheduler's run
 230          * queue for action.
 231          */
 232         ++runqcount;
 233         p->p_flag |= P_ONRUNQ;
 234         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
 235                 pri = p->p_priority >> 2;
 236                 q = &queues[pri];
 237                 queuebits |= 1 << pri;
 238         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
 239                    p->p_rtprio.type == RTP_PRIO_FIFO) {
 240                 pri = (u_int8_t)p->p_rtprio.prio;
 241                 q = &rtqueues[pri];
 242                 rtqueuebits |= 1 << pri;
 243         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
 244                 pri = (u_int8_t)p->p_rtprio.prio;
 245                 q = &idqueues[pri];
 246                 idqueuebits |= 1 << pri;
 247         } else {
 248                 panic("setrunqueue: invalid rtprio type");
 249         }
 250         KKASSERT(pri < 32);
 251         p->p_rqindex = pri;             /* remember the queue index */
 252         TAILQ_INSERT_TAIL(q, p, p_procq);
 253
 254         /*
 255          * Wakeup other cpus to schedule the newly available thread.
 256          * XXX doesn't really have to be in a critical section.
 257          * We own giant after all.
 258          *
 259          * We use rdyprocmask to avoid unnecessarily waking up the scheduler
 260          * thread when it is already running.
 261          */
 262         if ((mask = ~curprocmask & rdyprocmask & mycpu->gd_other_cpus) != 0 &&
 263             (p->p_flag & P_PASSIVE_ACQ) == 0) {
 264                 int count = runqcount;
 265                 if (!mask)
 266                         printf("PROC %d nocpu to schedule it on\n", p->p_pid);
 267                 while (mask && count) {
 268                         cpuid = bsfl(mask);
 269                         KKASSERT((curprocmask & (1 << cpuid)) == 0);
 270                         rdyprocmask &= ~(1 << cpuid);
 271                         lwkt_schedule(&globaldata_find(cpuid)->gd_schedthread);
 272                         --count;
 273                         mask &= ~(1 << cpuid);
 274                 }
 275         }
 276         crit_exit();
 277 }
 278
 279 /*
 280  * remrunqueue() removes a given process from the run queue that it is on,
 281  * clearing the queue busy bit if it becomes empty.  This function is called
 282  * when a userland process is selected for LWKT scheduling.  Note that
 283  * LWKT scheduling is an abstraction of 'curproc'.. there could very well be
 284  * several userland processes whos threads are scheduled or otherwise in
 285  * a special state, and such processes are NOT on the userland scheduler's
 286  * run queue.
 287  *
 288  * This must be called at splhigh().
 289  */
 290 void
 291 remrunqueue(struct proc *p)
 292 {
 293         struct rq *q;
 294         u_int32_t *which;
 295         u_int8_t pri;
 296
 297         crit_enter();
 298         KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq4!"));
 299         p->p_flag &= ~P_ONRUNQ;
 300         --runqcount;
 301         KKASSERT(runqcount >= 0);
 302         pri = p->p_rqindex;
 303         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
 304                 q = &queues[pri];
 305                 which = &queuebits;
 306         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
 307                    p->p_rtprio.type == RTP_PRIO_FIFO) {
 308                 q = &rtqueues[pri];
 309                 which = &rtqueuebits;
 310         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
 311                 q = &idqueues[pri];
 312                 which = &idqueuebits;
 313         } else {
 314                 panic("remrunqueue: invalid rtprio type");
 315         }
 316         TAILQ_REMOVE(q, p, p_procq);
 317         if (TAILQ_EMPTY(q)) {
 318                 KASSERT((*which & (1 << pri)) != 0,
 319                         ("remrunqueue: remove from empty queue"));
 320                 *which &= ~(1 << pri);
 321         }
 322         crit_exit();
 323 }
 324
 325 /*
 326  * Release the P_CURPROC designation on the CURRENT process only.  This
 327  * will allow another userland process to be scheduled.  If we do not
 328  * have or cannot get the MP lock we just wakeup the scheduler thread for
 329  * this cpu.
 330  *
 331  * WARNING!  The MP lock may be in an unsynchronized state due to the
 332  * way get_mplock() works and the fact that this function may be called
 333  * from a passive release during a lwkt_switch().   try_mplock() will deal
 334  * with this for us but you should be aware that td_mpcount may not be
 335  * useable.
 336  */
 337 void
 338 release_curproc(struct proc *p, int force)
 339 {
 340         int cpuid;
 341         struct proc *np;
 342
 343 #ifdef ONLY_ONE_USER_CPU
 344         KKASSERT(mycpu->gd_cpuid == 0 && p->p_thread->td_gd == mycpu);
 345 #endif
 346         crit_enter();
 347         clear_resched();
 348         cpuid = p->p_thread->td_gd->gd_cpuid;
 349         p->p_flag |= P_CP_RELEASED;
 350         if (p->p_flag & P_CURPROC) {
 351                 p->p_flag &= ~P_CURPROC;
 352                 if (try_mplock()) {
 353                         KKASSERT(curprocmask & (1 << cpuid));
 354                         if ((np = chooseproc()) != NULL) {
 355                                 if (force || test_resched(p, np)) {
 356                                         np->p_flag |= P_CURPROC;
 357                                         USCHED_COUNTER(np->p_thread);
 358                                         lwkt_acquire(np->p_thread);
 359                                         lwkt_schedule(np->p_thread);
 360                                 } else {
 361                                         p->p_flag &= ~P_CP_RELEASED;
 362                                         p->p_flag |= P_CURPROC;
 363                                         setrunqueue(np);
 364                                 }
 365                         } else {
 366                                 curprocmask &= ~(1 << cpuid);
 367                         }
 368                         rel_mplock();
 369                 } else {
 370                         KKASSERT(0);
 371                         curprocmask &= ~(1 << cpuid);
 372                         if (rdyprocmask & (1 << cpuid))
 373                                 lwkt_schedule(&globaldata_find(cpuid)->gd_schedthread);
 374                 }
 375         }
 376         crit_exit();
 377 }
 378
 379 /*
 380  * Acquire the P_CURPROC designation on the CURRENT process only.  This
 381  * function is called prior to returning to userland.  If the system
 382  * call or trap did not block and if no reschedule was requested it is
 383  * highly likely that the P_CURPROC flag is still set in the proc, and
 384  * we do almost nothing here.
 385  */
 386 void
 387 acquire_curproc(struct proc *p)
 388 {
 389         int cpuid;
 390         struct proc *np;
 391
 392         /*
 393          * Short cut, we've already acquired the designation or we never
 394          * lost it in the first place.
 395          */
 396         if ((p->p_flag & P_CURPROC) != 0)
 397                 return;
 398
 399         /*
 400          * Long cut.  This pulls in a bit of the userland scheduler as
 401          * an optimization.  If our cpu has not scheduled a userland
 402          * process we gladly fill the slot, otherwise we choose the best
 403          * candidate from the run queue and compare it against ourselves,
 404          * scheduling either us or him depending.
 405          *
 406          * If our cpu's slot isn't free we put ourselves on the userland
 407          * run queue and switch away.  We should have P_CURPROC when we
 408          * come back.  Note that a cpu change can occur when we come back.
 409          *
 410          * YYY don't need critical section, we hold giant and no interrupt
 411          * will mess w/ this proc?  Or will it?  What about curprocmask?
 412          */
 413 #ifdef ONLY_ONE_USER_CPU
 414         KKASSERT(mycpu->gd_cpuid == 0 && p->p_thread->td_gd == mycpu);
 415 #endif
 416         crit_enter();
 417         p->p_flag &= ~P_CP_RELEASED;
 418         while ((p->p_flag & P_CURPROC) == 0) {
 419                 cpuid = p->p_thread->td_gd->gd_cpuid;   /* load/reload cpuid */
 420                 if ((curprocmask & (1 << cpuid)) == 0) {
 421                         curprocmask |= 1 << cpuid;
 422                         if ((np = chooseproc()) != NULL) {
 423                                 KKASSERT((np->p_flag & P_CP_RELEASED) == 0);
 424                                 if (test_resched(p, np)) {
 425                                         np->p_flag |= P_CURPROC;
 426                                         USCHED_COUNTER(np->p_thread);
 427                                         lwkt_acquire(np->p_thread);
 428                                         lwkt_schedule(np->p_thread);
 429                                 } else {
 430                                         p->p_flag |= P_CURPROC;
 431                                         setrunqueue(np);
 432                                 }
 433                         } else {
 434                                 p->p_flag |= P_CURPROC;
 435                         }
 436                 }
 437                 if ((p->p_flag & P_CURPROC) == 0) {
 438                         lwkt_deschedule_self();
 439                         setrunqueue(p);
 440                         lwkt_switch();
 441                         KKASSERT((p->p_flag & (P_ONRUNQ|P_CURPROC|P_CP_RELEASED)) == P_CURPROC);
 442                 }
 443         }
 444         crit_exit();
 445 }
 446
 447 /*
 448  * Yield / synchronous reschedule.  This is a bit tricky because the trap
 449  * code might have set a lazy release on the switch function.  The first
 450  * thing we do is call lwkt_switch() to resolve the lazy release (if any).
 451  * Then, if we are a process, we want to allow another process to run.
 452  *
 453  * The only way to do that is to acquire and then release P_CURPROC.  We
 454  * have to release it because the kernel expects it to be released as a
 455  * sanity check when it goes to sleep.
 456  *
 457  * XXX we need a way to ensure that we wake up eventually from a yield,
 458  * even if we are an idprio process.
 459  */
 460 void
 461 uio_yield(void)
 462 {
 463         struct thread *td = curthread;
 464         struct proc *p = td->td_proc;
 465
 466         lwkt_switch();
 467         if (p) {
 468                 p->p_flag |= P_PASSIVE_ACQ;
 469                 acquire_curproc(p);
 470                 release_curproc(p, 1);
 471                 p->p_flag &= ~P_PASSIVE_ACQ;
 472         }
 473 }
 474
 475
 476 /*
 477  * For SMP systems a user scheduler helper thread is created for each
 478  * cpu and is used to allow one cpu to wakeup another for the purposes of
 479  * scheduling userland threads from setrunqueue().  UP systems do not
 480  * need the helper since there is only one cpu.  We can't use the idle
 481  * thread for this because we need to hold the MP lock.  Additionally,
 482  * doing things this way allows us to HLT idle cpus on MP systems.
 483  */
 484
 485 #ifdef SMP
 486
 487 static void
 488 sched_thread(void *dummy)
 489 {
 490     int cpuid = mycpu->gd_cpuid;        /* doesn't change */
 491     u_int32_t cpumask = 1 << cpuid;     /* doesn't change */
 492
 493 #ifdef ONLY_ONE_USER_CPU
 494     KKASSERT(cpuid == 0);
 495 #endif
 496
 497     get_mplock();                       /* hold the MP lock */
 498     for (;;) {
 499         struct proc *np;
 500
 501         lwkt_deschedule_self();         /* interlock */
 502         rdyprocmask |= cpumask;
 503         crit_enter();
 504         if ((curprocmask & cpumask) == 0 && (np = chooseproc()) != NULL) {
 505             curprocmask |= cpumask;
 506             np->p_flag |= P_CURPROC;
 507             USCHED_COUNTER(np->p_thread);
 508             lwkt_acquire(np->p_thread);
 509             lwkt_schedule(np->p_thread);
 510         }
 511         crit_exit();
 512         lwkt_switch();
 513     }
 514 }
 515
 516 void
 517 sched_thread_init(void)
 518 {
 519     int cpuid = mycpu->gd_cpuid;
 520
 521     lwkt_create(sched_thread, NULL, NULL, &mycpu->gd_schedthread,
 522         TDF_STOPREQ, "usched %d", cpuid);
 523     curprocmask &= ~(1 << cpuid);       /* schedule user proc on cpu */
 524 #ifdef ONLY_ONE_USER_CPU
 525     if (cpuid)
 526         curprocmask |= 1 << cpuid;      /* DISABLE USER PROCS */
 527 #endif
 528     rdyprocmask |= 1 << cpuid;
 529 }
 530
 531 #endif
 532