sys/kern/usched_bsd4.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  * $DragonFly: src/sys/kern/usched_bsd4.c,v 1.26 2008/11/01 23:31:19 dillon Exp $
  27  */
  28
  29 #include <sys/param.h>
  30 #include <sys/systm.h>
  31 #include <sys/kernel.h>
  32 #include <sys/lock.h>
  33 #include <sys/queue.h>
  34 #include <sys/proc.h>
  35 #include <sys/rtprio.h>
  36 #include <sys/uio.h>
  37 #include <sys/sysctl.h>
  38 #include <sys/resourcevar.h>
  39 #include <sys/spinlock.h>
  40 #include <machine/cpu.h>
  41 #include <machine/smp.h>
  42
  43 #include <sys/thread2.h>
  44 #include <sys/spinlock2.h>
  45 #include <sys/mplock2.h>
  46
  47 /*
  48  * Priorities.  Note that with 32 run queues per scheduler each queue
  49  * represents four priority levels.
  50  */
  51
  52 #define MAXPRI                  128
  53 #define PRIMASK                 (MAXPRI - 1)
  54 #define PRIBASE_REALTIME        0
  55 #define PRIBASE_NORMAL          MAXPRI
  56 #define PRIBASE_IDLE            (MAXPRI * 2)
  57 #define PRIBASE_THREAD          (MAXPRI * 3)
  58 #define PRIBASE_NULL            (MAXPRI * 4)
  59
  60 #define NQS     32                      /* 32 run queues. */
  61 #define PPQ     (MAXPRI / NQS)          /* priorities per queue */
  62 #define PPQMASK (PPQ - 1)
  63
  64 /*
  65  * NICEPPQ      - number of nice units per priority queue
  66  * ESTCPURAMP   - number of scheduler ticks for estcpu to switch queues
  67  *
  68  * ESTCPUPPQ    - number of estcpu units per priority queue
  69  * ESTCPUMAX    - number of estcpu units
  70  * ESTCPUINCR   - amount we have to increment p_estcpu per scheduling tick at
  71  *                100% cpu.
  72  */
  73 #define NICEPPQ         2
  74 #define ESTCPURAMP      4
  75 #define ESTCPUPPQ       512
  76 #define ESTCPUMAX       (ESTCPUPPQ * NQS)
  77 #define ESTCPUINCR      (ESTCPUPPQ / ESTCPURAMP)
  78 #define PRIO_RANGE      (PRIO_MAX - PRIO_MIN + 1)
  79
  80 #define ESTCPULIM(v)    min((v), ESTCPUMAX)
  81
  82 TAILQ_HEAD(rq, lwp);
  83
  84 #define lwp_priority    lwp_usdata.bsd4.priority
  85 #define lwp_rqindex     lwp_usdata.bsd4.rqindex
  86 #define lwp_origcpu     lwp_usdata.bsd4.origcpu
  87 #define lwp_estcpu      lwp_usdata.bsd4.estcpu
  88 #define lwp_rqtype      lwp_usdata.bsd4.rqtype
  89
  90 static void bsd4_acquire_curproc(struct lwp *lp);
  91 static void bsd4_release_curproc(struct lwp *lp);
  92 static void bsd4_select_curproc(globaldata_t gd);
  93 static void bsd4_setrunqueue(struct lwp *lp);
  94 static void bsd4_schedulerclock(struct lwp *lp, sysclock_t period,
  95                                 sysclock_t cpstamp);
  96 static void bsd4_recalculate_estcpu(struct lwp *lp);
  97 static void bsd4_resetpriority(struct lwp *lp);
  98 static void bsd4_forking(struct lwp *plp, struct lwp *lp);
  99 static void bsd4_exiting(struct lwp *plp, struct lwp *lp);
 100 static void bsd4_yield(struct lwp *lp);
 101
 102 #ifdef SMP
 103 static void need_user_resched_remote(void *dummy);
 104 #endif
 105 static struct lwp *chooseproc_locked(struct lwp *chklp);
 106 static void bsd4_remrunqueue_locked(struct lwp *lp);
 107 static void bsd4_setrunqueue_locked(struct lwp *lp);
 108
 109 struct usched usched_bsd4 = {
 110         { NULL },
 111         "bsd4", "Original DragonFly Scheduler",
 112         NULL,                   /* default registration */
 113         NULL,                   /* default deregistration */
 114         bsd4_acquire_curproc,
 115         bsd4_release_curproc,
 116         bsd4_setrunqueue,
 117         bsd4_schedulerclock,
 118         bsd4_recalculate_estcpu,
 119         bsd4_resetpriority,
 120         bsd4_forking,
 121         bsd4_exiting,
 122         NULL,                   /* setcpumask not supported */
 123         bsd4_yield
 124 };
 125
 126 struct usched_bsd4_pcpu {
 127         struct thread helper_thread;
 128         short   rrcount;
 129         short   upri;
 130         struct lwp *uschedcp;
 131 };
 132
 133 typedef struct usched_bsd4_pcpu *bsd4_pcpu_t;
 134
 135 /*
 136  * We have NQS (32) run queues per scheduling class.  For the normal
 137  * class, there are 128 priorities scaled onto these 32 queues.  New
 138  * processes are added to the last entry in each queue, and processes
 139  * are selected for running by taking them from the head and maintaining
 140  * a simple FIFO arrangement.  Realtime and Idle priority processes have
 141  * and explicit 0-31 priority which maps directly onto their class queue
 142  * index.  When a queue has something in it, the corresponding bit is
 143  * set in the queuebits variable, allowing a single read to determine
 144  * the state of all 32 queues and then a ffs() to find the first busy
 145  * queue.
 146  */
 147 static struct rq bsd4_queues[NQS];
 148 static struct rq bsd4_rtqueues[NQS];
 149 static struct rq bsd4_idqueues[NQS];
 150 static u_int32_t bsd4_queuebits;
 151 static u_int32_t bsd4_rtqueuebits;
 152 static u_int32_t bsd4_idqueuebits;
 153 static cpumask_t bsd4_curprocmask = -1; /* currently running a user process */
 154 static cpumask_t bsd4_rdyprocmask;      /* ready to accept a user process */
 155 static int       bsd4_runqcount;
 156 #ifdef SMP
 157 static volatile int bsd4_scancpu;
 158 #endif
 159 static struct spinlock bsd4_spin;
 160 static struct usched_bsd4_pcpu bsd4_pcpu[MAXCPU];
 161
 162 SYSCTL_INT(_debug, OID_AUTO, bsd4_runqcount, CTLFLAG_RD, &bsd4_runqcount, 0,
 163     "Number of run queues");
 164 #ifdef INVARIANTS
 165 static int usched_nonoptimal;
 166 SYSCTL_INT(_debug, OID_AUTO, usched_nonoptimal, CTLFLAG_RW,
 167         &usched_nonoptimal, 0, "acquire_curproc() was not optimal");
 168 static int usched_optimal;
 169 SYSCTL_INT(_debug, OID_AUTO, usched_optimal, CTLFLAG_RW,
 170         &usched_optimal, 0, "acquire_curproc() was optimal");
 171 #endif
 172 static int usched_debug = -1;
 173 SYSCTL_INT(_debug, OID_AUTO, scdebug, CTLFLAG_RW, &usched_debug, 0,
 174     "Print debug information for this pid");
 175 #ifdef SMP
 176 static int remote_resched_nonaffinity;
 177 static int remote_resched_affinity;
 178 static int choose_affinity;
 179 SYSCTL_INT(_debug, OID_AUTO, remote_resched_nonaffinity, CTLFLAG_RD,
 180         &remote_resched_nonaffinity, 0, "Number of remote rescheds");
 181 SYSCTL_INT(_debug, OID_AUTO, remote_resched_affinity, CTLFLAG_RD,
 182         &remote_resched_affinity, 0, "Number of remote rescheds");
 183 SYSCTL_INT(_debug, OID_AUTO, choose_affinity, CTLFLAG_RD,
 184         &choose_affinity, 0, "chooseproc() was smart");
 185 #endif
 186
 187 static int usched_bsd4_rrinterval = (ESTCPUFREQ + 9) / 10;
 188 SYSCTL_INT(_kern, OID_AUTO, usched_bsd4_rrinterval, CTLFLAG_RW,
 189         &usched_bsd4_rrinterval, 0, "");
 190 static int usched_bsd4_decay = ESTCPUINCR / 2;
 191 SYSCTL_INT(_kern, OID_AUTO, usched_bsd4_decay, CTLFLAG_RW,
 192         &usched_bsd4_decay, 0, "");
 193
 194 /*
 195  * Initialize the run queues at boot time.
 196  */
 197 static void
 198 rqinit(void *dummy)
 199 {
 200         int i;
 201
 202         spin_init(&bsd4_spin);
 203         for (i = 0; i < NQS; i++) {
 204                 TAILQ_INIT(&bsd4_queues[i]);
 205                 TAILQ_INIT(&bsd4_rtqueues[i]);
 206                 TAILQ_INIT(&bsd4_idqueues[i]);
 207         }
 208         atomic_clear_cpumask(&bsd4_curprocmask, 1);
 209 }
 210 SYSINIT(runqueue, SI_BOOT2_USCHED, SI_ORDER_FIRST, rqinit, NULL)
 211
 212 /*
 213  * BSD4_ACQUIRE_CURPROC
 214  *
 215  * This function is called when the kernel intends to return to userland.
 216  * It is responsible for making the thread the current designated userland
 217  * thread for this cpu, blocking if necessary.
 218  *
 219  * The kernel has already depressed our LWKT priority so we must not switch
 220  * until we have either assigned or disposed of the thread.
 221  *
 222  * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE
 223  * TO ANOTHER CPU!  Because most of the kernel assumes that no migration will
 224  * occur, this function is called only under very controlled circumstances.
 225  *
 226  * MPSAFE
 227  */
 228 static void
 229 bsd4_acquire_curproc(struct lwp *lp)
 230 {
 231         globaldata_t gd;
 232         bsd4_pcpu_t dd;
 233         struct lwp *olp;
 234
 235         crit_enter();
 236         bsd4_recalculate_estcpu(lp);
 237
 238         /*
 239          * If a reschedule was requested give another thread the
 240          * driver's seat.
 241          */
 242         if (user_resched_wanted()) {
 243                 clear_user_resched();
 244                 bsd4_release_curproc(lp);
 245         }
 246
 247         /*
 248          * Loop until we are the current user thread
 249          */
 250         do {
 251                 /*
 252                  * Reload after a switch or setrunqueue/switch possibly
 253                  * moved us to another cpu.
 254                  */
 255                 /*clear_lwkt_resched();*/
 256                 gd = mycpu;
 257                 dd = &bsd4_pcpu[gd->gd_cpuid];
 258
 259                 /*
 260                  * Become the currently scheduled user thread for this cpu
 261                  * if we can do so trivially.
 262                  *
 263                  * We can steal another thread's current thread designation
 264                  * on this cpu since if we are running that other thread
 265                  * must not be, so we can safely deschedule it.
 266                  */
 267                 if (dd->uschedcp == lp) {
 268                         /*
 269                          * We are already the current lwp (hot path).
 270                          */
 271                         dd->upri = lp->lwp_priority;
 272                 } else if (dd->uschedcp == NULL) {
 273                         /*
 274                          * We can trivially become the current lwp.
 275                          */
 276                         atomic_set_cpumask(&bsd4_curprocmask, gd->gd_cpumask);
 277                         dd->uschedcp = lp;
 278                         dd->upri = lp->lwp_priority;
 279                 } else if (dd->upri > lp->lwp_priority) {
 280                         /*
 281                          * We can steal the current lwp designation from the
 282                          * olp that was previously assigned to this cpu.
 283                          */
 284                         olp = dd->uschedcp;
 285                         dd->uschedcp = lp;
 286                         dd->upri = lp->lwp_priority;
 287                         lwkt_deschedule(olp->lwp_thread);
 288                         bsd4_setrunqueue(olp);
 289                 } else {
 290                         /*
 291                          * We cannot become the current lwp, place the lp
 292                          * on the bsd4 run-queue and deschedule ourselves.
 293                          */
 294                         lwkt_deschedule(lp->lwp_thread);
 295                         bsd4_setrunqueue(lp);
 296                         lwkt_switch();
 297                 }
 298
 299                 /*
 300                  * Other threads at our current user priority have already
 301                  * put in their bids, but we must run any kernel threads
 302                  * at higher priorities, and we could lose our bid to
 303                  * another thread trying to return to user mode in the
 304                  * process.
 305                  *
 306                  * If we lose our bid we will be descheduled and put on
 307                  * the run queue.  When we are reactivated we will have
 308                  * another chance.
 309                  */
 310                 if (lwkt_resched_wanted() ||
 311                     lp->lwp_thread->td_fairq_accum < 0) {
 312                         lwkt_switch();
 313                 }
 314         } while (dd->uschedcp != lp);
 315
 316         crit_exit();
 317         KKASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0);
 318 }
 319
 320 /*
 321  * BSD4_RELEASE_CURPROC
 322  *
 323  * This routine detaches the current thread from the userland scheduler,
 324  * usually because the thread needs to run or block in the kernel (at
 325  * kernel priority) for a while.
 326  *
 327  * This routine is also responsible for selecting a new thread to
 328  * make the current thread.
 329  *
 330  * NOTE: This implementation differs from the dummy example in that
 331  * bsd4_select_curproc() is able to select the current process, whereas
 332  * dummy_select_curproc() is not able to select the current process.
 333  * This means we have to NULL out uschedcp.
 334  *
 335  * Additionally, note that we may already be on a run queue if releasing
 336  * via the lwkt_switch() in bsd4_setrunqueue().
 337  *
 338  * MPSAFE
 339  */
 340 static void
 341 bsd4_release_curproc(struct lwp *lp)
 342 {
 343         globaldata_t gd = mycpu;
 344         bsd4_pcpu_t dd = &bsd4_pcpu[gd->gd_cpuid];
 345
 346         if (dd->uschedcp == lp) {
 347                 crit_enter();
 348                 KKASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0);
 349                 dd->uschedcp = NULL;    /* don't let lp be selected */
 350                 dd->upri = PRIBASE_NULL;
 351                 atomic_clear_cpumask(&bsd4_curprocmask, gd->gd_cpumask);
 352                 bsd4_select_curproc(gd);
 353                 crit_exit();
 354         }
 355 }
 356
 357 /*
 358  * BSD4_SELECT_CURPROC
 359  *
 360  * Select a new current process for this cpu and clear any pending user
 361  * reschedule request.  The cpu currently has no current process.
 362  *
 363  * This routine is also responsible for equal-priority round-robining,
 364  * typically triggered from bsd4_schedulerclock().  In our dummy example
 365  * all the 'user' threads are LWKT scheduled all at once and we just
 366  * call lwkt_switch().
 367  *
 368  * The calling process is not on the queue and cannot be selected.
 369  *
 370  * MPSAFE
 371  */
 372 static
 373 void
 374 bsd4_select_curproc(globaldata_t gd)
 375 {
 376         bsd4_pcpu_t dd = &bsd4_pcpu[gd->gd_cpuid];
 377         struct lwp *nlp;
 378         int cpuid = gd->gd_cpuid;
 379
 380         crit_enter_gd(gd);
 381
 382         spin_lock(&bsd4_spin);
 383         if ((nlp = chooseproc_locked(dd->uschedcp)) != NULL) {
 384                 atomic_set_cpumask(&bsd4_curprocmask, CPUMASK(cpuid));
 385                 dd->upri = nlp->lwp_priority;
 386                 dd->uschedcp = nlp;
 387                 spin_unlock(&bsd4_spin);
 388 #ifdef SMP
 389                 lwkt_acquire(nlp->lwp_thread);
 390 #endif
 391                 lwkt_schedule(nlp->lwp_thread);
 392         } else {
 393                 spin_unlock(&bsd4_spin);
 394         }
 395 #if 0
 396         } else if (bsd4_runqcount && (bsd4_rdyprocmask & CPUMASK(cpuid))) {
 397                 atomic_clear_cpumask(&bsd4_rdyprocmask, CPUMASK(cpuid));
 398                 spin_unlock(&bsd4_spin);
 399                 lwkt_schedule(&dd->helper_thread);
 400         } else {
 401                 spin_unlock(&bsd4_spin);
 402         }
 403 #endif
 404         crit_exit_gd(gd);
 405 }
 406
 407 /*
 408  * BSD4_SETRUNQUEUE
 409  *
 410  * Place the specified lwp on the user scheduler's run queue.  This routine
 411  * must be called with the thread descheduled.  The lwp must be runnable.
 412  *
 413  * The thread may be the current thread as a special case.
 414  *
 415  * MPSAFE
 416  */
 417 static void
 418 bsd4_setrunqueue(struct lwp *lp)
 419 {
 420         globaldata_t gd;
 421         bsd4_pcpu_t dd;
 422 #ifdef SMP
 423         int cpuid;
 424         cpumask_t mask;
 425         cpumask_t tmpmask;
 426 #endif
 427
 428         /*
 429          * First validate the process state relative to the current cpu.
 430          * We don't need the spinlock for this, just a critical section.
 431          * We are in control of the process.
 432          */
 433         crit_enter();
 434         KASSERT(lp->lwp_stat == LSRUN, ("setrunqueue: lwp not LSRUN"));
 435         KASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0,
 436             ("lwp %d/%d already on runq! flag %08x/%08x", lp->lwp_proc->p_pid,
 437              lp->lwp_tid, lp->lwp_proc->p_flag, lp->lwp_flag));
 438         KKASSERT((lp->lwp_thread->td_flags & TDF_RUNQ) == 0);
 439
 440         /*
 441          * Note: gd and dd are relative to the target thread's last cpu,
 442          * NOT our current cpu.
 443          */
 444         gd = lp->lwp_thread->td_gd;
 445         dd = &bsd4_pcpu[gd->gd_cpuid];
 446
 447         /*
 448          * This process is not supposed to be scheduled anywhere or assigned
 449          * as the current process anywhere.  Assert the condition.
 450          */
 451         KKASSERT(dd->uschedcp != lp);
 452
 453 #ifndef SMP
 454         /*
 455          * If we are not SMP we do not have a scheduler helper to kick
 456          * and must directly activate the process if none are scheduled.
 457          *
 458          * This is really only an issue when bootstrapping init since
 459          * the caller in all other cases will be a user process, and
 460          * even if released (dd->uschedcp == NULL), that process will
 461          * kickstart the scheduler when it returns to user mode from
 462          * the kernel.
 463          */
 464         if (dd->uschedcp == NULL) {
 465                 atomic_set_cpumask(&bsd4_curprocmask, gd->gd_cpumask);
 466                 dd->uschedcp = lp;
 467                 dd->upri = lp->lwp_priority;
 468                 lwkt_schedule(lp->lwp_thread);
 469                 crit_exit();
 470                 return;
 471         }
 472 #endif
 473
 474 #ifdef SMP
 475         /*
 476          * XXX fixme.  Could be part of a remrunqueue/setrunqueue
 477          * operation when the priority is recalculated, so TDF_MIGRATING
 478          * may already be set.
 479          */
 480         if ((lp->lwp_thread->td_flags & TDF_MIGRATING) == 0)
 481                 lwkt_giveaway(lp->lwp_thread);
 482 #endif
 483
 484         /*
 485          * We lose control of lp the moment we release the spinlock after
 486          * having placed lp on the queue.  i.e. another cpu could pick it
 487          * up and it could exit, or its priority could be further adjusted,
 488          * or something like that.
 489          */
 490         spin_lock(&bsd4_spin);
 491         bsd4_setrunqueue_locked(lp);
 492
 493 #ifdef SMP
 494         /*
 495          * Kick the scheduler helper on one of the other cpu's
 496          * and request a reschedule if appropriate.
 497          *
 498          * NOTE: We check all cpus whos rdyprocmask is set.  First we
 499          *       look for cpus without designated lps, then we look for
 500          *       cpus with designated lps with a worse priority than our
 501          *       process.
 502          */
 503         ++bsd4_scancpu;
 504         cpuid = (bsd4_scancpu & 0xFFFF) % ncpus;
 505         mask = ~bsd4_curprocmask & bsd4_rdyprocmask & lp->lwp_cpumask &
 506                smp_active_mask & usched_global_cpumask;
 507
 508         while (mask) {
 509                 tmpmask = ~(CPUMASK(cpuid) - 1);
 510                 if (mask & tmpmask)
 511                         cpuid = BSFCPUMASK(mask & tmpmask);
 512                 else
 513                         cpuid = BSFCPUMASK(mask);
 514                 gd = globaldata_find(cpuid);
 515                 dd = &bsd4_pcpu[cpuid];
 516
 517                 if ((dd->upri & ~PPQMASK) >= (lp->lwp_priority & ~PPQMASK))
 518                         goto found;
 519                 mask &= ~CPUMASK(cpuid);
 520         }
 521
 522         /*
 523          * Then cpus which might have a currently running lp
 524          */
 525         mask = bsd4_curprocmask & bsd4_rdyprocmask &
 526                lp->lwp_cpumask & smp_active_mask & usched_global_cpumask;
 527
 528         while (mask) {
 529                 tmpmask = ~(CPUMASK(cpuid) - 1);
 530                 if (mask & tmpmask)
 531                         cpuid = BSFCPUMASK(mask & tmpmask);
 532                 else
 533                         cpuid = BSFCPUMASK(mask);
 534                 gd = globaldata_find(cpuid);
 535                 dd = &bsd4_pcpu[cpuid];
 536
 537                 if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK))
 538                         goto found;
 539                 mask &= ~CPUMASK(cpuid);
 540         }
 541
 542         /*
 543          * If we cannot find a suitable cpu we reload from bsd4_scancpu
 544          * and round-robin.  Other cpus will pickup as they release their
 545          * current lwps or become ready.
 546          *
 547          * Avoid a degenerate system lockup case if usched_global_cpumask
 548          * is set to 0 or otherwise does not cover lwp_cpumask.
 549          *
 550          * We only kick the target helper thread in this case, we do not
 551          * set the user resched flag because
 552          */
 553         cpuid = (bsd4_scancpu & 0xFFFF) % ncpus;
 554         if ((CPUMASK(cpuid) & usched_global_cpumask) == 0) {
 555                 cpuid = 0;
 556         }
 557         gd = globaldata_find(cpuid);
 558         dd = &bsd4_pcpu[cpuid];
 559 found:
 560         if (gd == mycpu) {
 561                 spin_unlock(&bsd4_spin);
 562                 if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) {
 563                         if (dd->uschedcp == NULL) {
 564                                 lwkt_schedule(&dd->helper_thread);
 565                         } else {
 566                                 need_user_resched();
 567                         }
 568                 }
 569         } else {
 570                 atomic_clear_cpumask(&bsd4_rdyprocmask, CPUMASK(cpuid));
 571                 spin_unlock(&bsd4_spin);
 572                 if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK))
 573                         lwkt_send_ipiq(gd, need_user_resched_remote, NULL);
 574                 else
 575                         lwkt_schedule(&dd->helper_thread);
 576         }
 577 #else
 578         /*
 579          * Request a reschedule if appropriate.
 580          */
 581         spin_unlock(&bsd4_spin);
 582         if ((dd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) {
 583                 need_user_resched();
 584         }
 585 #endif
 586         crit_exit();
 587 }
 588
 589 /*
 590  * This routine is called from a systimer IPI.  It MUST be MP-safe and
 591  * the BGL IS NOT HELD ON ENTRY.  This routine is called at ESTCPUFREQ on
 592  * each cpu.
 593  *
 594  * MPSAFE
 595  */
 596 static
 597 void
 598 bsd4_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp)
 599 {
 600         globaldata_t gd = mycpu;
 601         bsd4_pcpu_t dd = &bsd4_pcpu[gd->gd_cpuid];
 602
 603         /*
 604          * Do we need to round-robin?  We round-robin 10 times a second.
 605          * This should only occur for cpu-bound batch processes.
 606          */
 607         if (++dd->rrcount >= usched_bsd4_rrinterval) {
 608                 dd->rrcount = 0;
 609                 need_user_resched();
 610         }
 611
 612         /*
 613          * As the process accumulates cpu time p_estcpu is bumped and may
 614          * push the process into another scheduling queue.  It typically
 615          * takes 4 ticks to bump the queue.
 616          */
 617         lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUINCR);
 618
 619         /*
 620          * Reducing p_origcpu over time causes more of our estcpu to be
 621          * returned to the parent when we exit.  This is a small tweak
 622          * for the batch detection heuristic.
 623          */
 624         if (lp->lwp_origcpu)
 625                 --lp->lwp_origcpu;
 626
 627         /*
 628          * Spinlocks also hold a critical section so there should not be
 629          * any active.
 630          */
 631         KKASSERT(gd->gd_spinlocks_wr == 0);
 632
 633         bsd4_resetpriority(lp);
 634 #if 0
 635         /*
 636         * if we can't call bsd4_resetpriority for some reason we must call
 637          * need user_resched().
 638          */
 639         need_user_resched();
 640 #endif
 641 }
 642
 643 /*
 644  * Called from acquire and from kern_synch's one-second timer (one of the
 645  * callout helper threads) with a critical section held.
 646  *
 647  * Decay p_estcpu based on the number of ticks we haven't been running
 648  * and our p_nice.  As the load increases each process observes a larger
 649  * number of idle ticks (because other processes are running in them).
 650  * This observation leads to a larger correction which tends to make the
 651  * system more 'batchy'.
 652  *
 653  * Note that no recalculation occurs for a process which sleeps and wakes
 654  * up in the same tick.  That is, a system doing thousands of context
 655  * switches per second will still only do serious estcpu calculations
 656  * ESTCPUFREQ times per second.
 657  *
 658  * MPSAFE
 659  */
 660 static
 661 void
 662 bsd4_recalculate_estcpu(struct lwp *lp)
 663 {
 664         globaldata_t gd = mycpu;
 665         sysclock_t cpbase;
 666         int loadfac;
 667         int ndecay;
 668         int nticks;
 669         int nleft;
 670
 671         /*
 672          * We have to subtract periodic to get the last schedclock
 673          * timeout time, otherwise we would get the upcoming timeout.
 674          * Keep in mind that a process can migrate between cpus and
 675          * while the scheduler clock should be very close, boundary
 676          * conditions could lead to a small negative delta.
 677          */
 678         cpbase = gd->gd_schedclock.time - gd->gd_schedclock.periodic;
 679
 680         if (lp->lwp_slptime > 1) {
 681                 /*
 682                  * Too much time has passed, do a coarse correction.
 683                  */
 684                 lp->lwp_estcpu = lp->lwp_estcpu >> 1;
 685                 bsd4_resetpriority(lp);
 686                 lp->lwp_cpbase = cpbase;
 687                 lp->lwp_cpticks = 0;
 688         } else if (lp->lwp_cpbase != cpbase) {
 689                 /*
 690                  * Adjust estcpu if we are in a different tick.  Don't waste
 691                  * time if we are in the same tick.
 692                  *
 693                  * First calculate the number of ticks in the measurement
 694                  * interval.  The nticks calculation can wind up 0 due to
 695                  * a bug in the handling of lwp_slptime  (as yet not found),
 696                  * so make sure we do not get a divide by 0 panic.
 697                  */
 698                 nticks = (cpbase - lp->lwp_cpbase) / gd->gd_schedclock.periodic;
 699                 if (nticks <= 0)
 700                         nticks = 1;
 701                 updatepcpu(lp, lp->lwp_cpticks, nticks);
 702
 703                 if ((nleft = nticks - lp->lwp_cpticks) < 0)
 704                         nleft = 0;
 705                 if (usched_debug == lp->lwp_proc->p_pid) {
 706                         kprintf("pid %d tid %d estcpu %d cpticks %d nticks %d nleft %d",
 707                                 lp->lwp_proc->p_pid, lp->lwp_tid, lp->lwp_estcpu,
 708                                 lp->lwp_cpticks, nticks, nleft);
 709                 }
 710
 711                 /*
 712                  * Calculate a decay value based on ticks remaining scaled
 713                  * down by the instantanious load and p_nice.
 714                  */
 715                 if ((loadfac = bsd4_runqcount) < 2)
 716                         loadfac = 2;
 717                 ndecay = nleft * usched_bsd4_decay * 2 *
 718                         (PRIO_MAX * 2 - lp->lwp_proc->p_nice) / (loadfac * PRIO_MAX * 2);
 719
 720                 /*
 721                  * Adjust p_estcpu.  Handle a border case where batch jobs
 722                  * can get stalled long enough to decay to zero when they
 723                  * shouldn't.
 724                  */
 725                 if (lp->lwp_estcpu > ndecay * 2)
 726                         lp->lwp_estcpu -= ndecay;
 727                 else
 728                         lp->lwp_estcpu >>= 1;
 729
 730                 if (usched_debug == lp->lwp_proc->p_pid)
 731                         kprintf(" ndecay %d estcpu %d\n", ndecay, lp->lwp_estcpu);
 732                 bsd4_resetpriority(lp);
 733                 lp->lwp_cpbase = cpbase;
 734                 lp->lwp_cpticks = 0;
 735         }
 736 }
 737
 738 /*
 739  * Compute the priority of a process when running in user mode.
 740  * Arrange to reschedule if the resulting priority is better
 741  * than that of the current process.
 742  *
 743  * This routine may be called with any process.
 744  *
 745  * This routine is called by fork1() for initial setup with the process
 746  * of the run queue, and also may be called normally with the process on or
 747  * off the run queue.
 748  *
 749  * MPSAFE
 750  */
 751 static void
 752 bsd4_resetpriority(struct lwp *lp)
 753 {
 754         bsd4_pcpu_t dd;
 755         int newpriority;
 756         u_short newrqtype;
 757         int reschedcpu;
 758
 759         /*
 760          * Calculate the new priority and queue type
 761          */
 762         crit_enter();
 763         spin_lock(&bsd4_spin);
 764
 765         newrqtype = lp->lwp_rtprio.type;
 766
 767         switch(newrqtype) {
 768         case RTP_PRIO_REALTIME:
 769         case RTP_PRIO_FIFO:
 770                 newpriority = PRIBASE_REALTIME +
 771                              (lp->lwp_rtprio.prio & PRIMASK);
 772                 break;
 773         case RTP_PRIO_NORMAL:
 774                 newpriority = (lp->lwp_proc->p_nice - PRIO_MIN) * PPQ / NICEPPQ;
 775                 newpriority += lp->lwp_estcpu * PPQ / ESTCPUPPQ;
 776                 newpriority = newpriority * MAXPRI / (PRIO_RANGE * PPQ /
 777                               NICEPPQ + ESTCPUMAX * PPQ / ESTCPUPPQ);
 778                 newpriority = PRIBASE_NORMAL + (newpriority & PRIMASK);
 779                 break;
 780         case RTP_PRIO_IDLE:
 781                 newpriority = PRIBASE_IDLE + (lp->lwp_rtprio.prio & PRIMASK);
 782                 break;
 783         case RTP_PRIO_THREAD:
 784                 newpriority = PRIBASE_THREAD + (lp->lwp_rtprio.prio & PRIMASK);
 785                 break;
 786         default:
 787                 panic("Bad RTP_PRIO %d", newrqtype);
 788                 /* NOT REACHED */
 789         }
 790
 791         /*
 792          * The newpriority incorporates the queue type so do a simple masked
 793          * check to determine if the process has moved to another queue.  If
 794          * it has, and it is currently on a run queue, then move it.
 795          */
 796         if ((lp->lwp_priority ^ newpriority) & ~PPQMASK) {
 797                 lp->lwp_priority = newpriority;
 798                 if (lp->lwp_flag & LWP_ONRUNQ) {
 799                         bsd4_remrunqueue_locked(lp);
 800                         lp->lwp_rqtype = newrqtype;
 801                         lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ;
 802                         bsd4_setrunqueue_locked(lp);
 803                         reschedcpu = lp->lwp_thread->td_gd->gd_cpuid;
 804                 } else {
 805                         lp->lwp_rqtype = newrqtype;
 806                         lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ;
 807                         reschedcpu = -1;
 808                 }
 809         } else {
 810                 lp->lwp_priority = newpriority;
 811                 reschedcpu = -1;
 812         }
 813
 814         /*
 815          * Determine if we need to reschedule the target cpu.  This only
 816          * occurs if the LWP is already on a scheduler queue, which means
 817          * that idle cpu notification has already occured.  At most we
 818          * need only issue a need_user_resched() on the appropriate cpu.
 819          *
 820          * The LWP may be owned by a CPU different from the current one,
 821          * in which case dd->uschedcp may be modified without an MP lock
 822          * or a spinlock held.  The worst that happens is that the code
 823          * below causes a spurious need_user_resched() on the target CPU
 824          * and dd->pri to be wrong for a short period of time, both of
 825          * which are harmless.
 826          */
 827         if (reschedcpu >= 0) {
 828                 dd = &bsd4_pcpu[reschedcpu];
 829                 if ((bsd4_rdyprocmask & CPUMASK(reschedcpu)) &&
 830                     (dd->upri & ~PRIMASK) > (lp->lwp_priority & ~PRIMASK)) {
 831 #ifdef SMP
 832                         if (reschedcpu == mycpu->gd_cpuid) {
 833                                 spin_unlock(&bsd4_spin);
 834                                 need_user_resched();
 835                         } else {
 836                                 spin_unlock(&bsd4_spin);
 837                                 atomic_clear_cpumask(&bsd4_rdyprocmask,
 838                                                      CPUMASK(reschedcpu));
 839                                 lwkt_send_ipiq(lp->lwp_thread->td_gd,
 840                                                need_user_resched_remote, NULL);
 841                         }
 842 #else
 843                         spin_unlock(&bsd4_spin);
 844                         need_user_resched();
 845 #endif
 846                 } else {
 847                         spin_unlock(&bsd4_spin);
 848                 }
 849         } else {
 850                 spin_unlock(&bsd4_spin);
 851         }
 852         crit_exit();
 853 }
 854
 855 /*
 856  * MPSAFE
 857  */
 858 static
 859 void
 860 bsd4_yield(struct lwp *lp)
 861 {
 862 #if 0
 863         /* FUTURE (or something similar) */
 864         switch(lp->lwp_rqtype) {
 865         case RTP_PRIO_NORMAL:
 866                 lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUINCR);
 867                 break;
 868         default:
 869                 break;
 870         }
 871 #endif
 872         need_user_resched();
 873 }
 874
 875 /*
 876  * Called from fork1() when a new child process is being created.
 877  *
 878  * Give the child process an initial estcpu that is more batch then
 879  * its parent and dock the parent for the fork (but do not
 880  * reschedule the parent).   This comprises the main part of our batch
 881  * detection heuristic for both parallel forking and sequential execs.
 882  *
 883  * Interactive processes will decay the boosted estcpu quickly while batch
 884  * processes will tend to compound it.
 885  * XXX lwp should be "spawning" instead of "forking"
 886  *
 887  * MPSAFE
 888  */
 889 static void
 890 bsd4_forking(struct lwp *plp, struct lwp *lp)
 891 {
 892         lp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ);
 893         lp->lwp_origcpu = lp->lwp_estcpu;
 894         plp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ);
 895 }
 896
 897 /*
 898  * Called when the parent reaps a child.   Propogate cpu use by the child
 899  * back to the parent.
 900  *
 901  * MPSAFE
 902  */
 903 static void
 904 bsd4_exiting(struct lwp *plp, struct lwp *lp)
 905 {
 906         int delta;
 907
 908         if (plp->lwp_proc->p_pid != 1) {
 909                 delta = lp->lwp_estcpu - lp->lwp_origcpu;
 910                 if (delta > 0)
 911                         plp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + delta);
 912         }
 913 }
 914
 915
 916 /*
 917  * chooseproc() is called when a cpu needs a user process to LWKT schedule,
 918  * it selects a user process and returns it.  If chklp is non-NULL and chklp
 919  * has a better or equal priority then the process that would otherwise be
 920  * chosen, NULL is returned.
 921  *
 922  * Until we fix the RUNQ code the chklp test has to be strict or we may
 923  * bounce between processes trying to acquire the current process designation.
 924  *
 925  * MPSAFE - must be called with bsd4_spin exclusive held.  The spinlock is
 926  *          left intact through the entire routine.
 927  */
 928 static
 929 struct lwp *
 930 chooseproc_locked(struct lwp *chklp)
 931 {
 932         struct lwp *lp;
 933         struct rq *q;
 934         u_int32_t *which, *which2;
 935         u_int32_t pri;
 936         u_int32_t rtqbits;
 937         u_int32_t tsqbits;
 938         u_int32_t idqbits;
 939         cpumask_t cpumask;
 940
 941         rtqbits = bsd4_rtqueuebits;
 942         tsqbits = bsd4_queuebits;
 943         idqbits = bsd4_idqueuebits;
 944         cpumask = mycpu->gd_cpumask;
 945
 946 #ifdef SMP
 947 again:
 948 #endif
 949         if (rtqbits) {
 950                 pri = bsfl(rtqbits);
 951                 q = &bsd4_rtqueues[pri];
 952                 which = &bsd4_rtqueuebits;
 953                 which2 = &rtqbits;
 954         } else if (tsqbits) {
 955                 pri = bsfl(tsqbits);
 956                 q = &bsd4_queues[pri];
 957                 which = &bsd4_queuebits;
 958                 which2 = &tsqbits;
 959         } else if (idqbits) {
 960                 pri = bsfl(idqbits);
 961                 q = &bsd4_idqueues[pri];
 962                 which = &bsd4_idqueuebits;
 963                 which2 = &idqbits;
 964         } else {
 965                 return NULL;
 966         }
 967         lp = TAILQ_FIRST(q);
 968         KASSERT(lp, ("chooseproc: no lwp on busy queue"));
 969
 970 #ifdef SMP
 971         while ((lp->lwp_cpumask & cpumask) == 0) {
 972                 lp = TAILQ_NEXT(lp, lwp_procq);
 973                 if (lp == NULL) {
 974                         *which2 &= ~(1 << pri);
 975                         goto again;
 976                 }
 977         }
 978 #endif
 979
 980         /*
 981          * If the passed lwp <chklp> is reasonably close to the selected
 982          * lwp <lp>, return NULL (indicating that <chklp> should be kept).
 983          *
 984          * Note that we must error on the side of <chklp> to avoid bouncing
 985          * between threads in the acquire code.
 986          */
 987         if (chklp) {
 988                 if (chklp->lwp_priority < lp->lwp_priority + PPQ)
 989                         return(NULL);
 990         }
 991
 992 #ifdef SMP
 993         /*
 994          * If the chosen lwp does not reside on this cpu spend a few
 995          * cycles looking for a better candidate at the same priority level.
 996          * This is a fallback check, setrunqueue() tries to wakeup the
 997          * correct cpu and is our front-line affinity.
 998          */
 999         if (lp->lwp_thread->td_gd != mycpu &&
1000             (chklp = TAILQ_NEXT(lp, lwp_procq)) != NULL
1001         ) {
1002                 if (chklp->lwp_thread->td_gd == mycpu) {
1003                         ++choose_affinity;
1004                         lp = chklp;
1005                 }
1006         }
1007 #endif
1008
1009         TAILQ_REMOVE(q, lp, lwp_procq);
1010         --bsd4_runqcount;
1011         if (TAILQ_EMPTY(q))
1012                 *which &= ~(1 << pri);
1013         KASSERT((lp->lwp_flag & LWP_ONRUNQ) != 0, ("not on runq6!"));
1014         lp->lwp_flag &= ~LWP_ONRUNQ;
1015         return lp;
1016 }
1017
1018 #ifdef SMP
1019
1020 static
1021 void
1022 need_user_resched_remote(void *dummy)
1023 {
1024         globaldata_t gd = mycpu;
1025         bsd4_pcpu_t  dd = &bsd4_pcpu[gd->gd_cpuid];
1026
1027         need_user_resched();
1028         lwkt_schedule(&dd->helper_thread);
1029 }
1030
1031 #endif
1032
1033 /*
1034  * bsd4_remrunqueue_locked() removes a given process from the run queue
1035  * that it is on, clearing the queue busy bit if it becomes empty.
1036  *
1037  * Note that user process scheduler is different from the LWKT schedule.
1038  * The user process scheduler only manages user processes but it uses LWKT
1039  * underneath, and a user process operating in the kernel will often be
1040  * 'released' from our management.
1041  *
1042  * MPSAFE - bsd4_spin must be held exclusively on call
1043  */
1044 static void
1045 bsd4_remrunqueue_locked(struct lwp *lp)
1046 {
1047         struct rq *q;
1048         u_int32_t *which;
1049         u_int8_t pri;
1050
1051         KKASSERT(lp->lwp_flag & LWP_ONRUNQ);
1052         lp->lwp_flag &= ~LWP_ONRUNQ;
1053         --bsd4_runqcount;
1054         KKASSERT(bsd4_runqcount >= 0);
1055
1056         pri = lp->lwp_rqindex;
1057         switch(lp->lwp_rqtype) {
1058         case RTP_PRIO_NORMAL:
1059                 q = &bsd4_queues[pri];
1060                 which = &bsd4_queuebits;
1061                 break;
1062         case RTP_PRIO_REALTIME:
1063         case RTP_PRIO_FIFO:
1064                 q = &bsd4_rtqueues[pri];
1065                 which = &bsd4_rtqueuebits;
1066                 break;
1067         case RTP_PRIO_IDLE:
1068                 q = &bsd4_idqueues[pri];
1069                 which = &bsd4_idqueuebits;
1070                 break;
1071         default:
1072                 panic("remrunqueue: invalid rtprio type");
1073                 /* NOT REACHED */
1074         }
1075         TAILQ_REMOVE(q, lp, lwp_procq);
1076         if (TAILQ_EMPTY(q)) {
1077                 KASSERT((*which & (1 << pri)) != 0,
1078                         ("remrunqueue: remove from empty queue"));
1079                 *which &= ~(1 << pri);
1080         }
1081 }
1082
1083 /*
1084  * bsd4_setrunqueue_locked()
1085  *
1086  * Add a process whos rqtype and rqindex had previously been calculated
1087  * onto the appropriate run queue.   Determine if the addition requires
1088  * a reschedule on a cpu and return the cpuid or -1.
1089  *
1090  * NOTE: Lower priorities are better priorities.
1091  *
1092  * MPSAFE - bsd4_spin must be held exclusively on call
1093  */
1094 static void
1095 bsd4_setrunqueue_locked(struct lwp *lp)
1096 {
1097         struct rq *q;
1098         u_int32_t *which;
1099         int pri;
1100
1101         KKASSERT((lp->lwp_flag & LWP_ONRUNQ) == 0);
1102         lp->lwp_flag |= LWP_ONRUNQ;
1103         ++bsd4_runqcount;
1104
1105         pri = lp->lwp_rqindex;
1106
1107         switch(lp->lwp_rqtype) {
1108         case RTP_PRIO_NORMAL:
1109                 q = &bsd4_queues[pri];
1110                 which = &bsd4_queuebits;
1111                 break;
1112         case RTP_PRIO_REALTIME:
1113         case RTP_PRIO_FIFO:
1114                 q = &bsd4_rtqueues[pri];
1115                 which = &bsd4_rtqueuebits;
1116                 break;
1117         case RTP_PRIO_IDLE:
1118                 q = &bsd4_idqueues[pri];
1119                 which = &bsd4_idqueuebits;
1120                 break;
1121         default:
1122                 panic("remrunqueue: invalid rtprio type");
1123                 /* NOT REACHED */
1124         }
1125
1126         /*
1127          * Add to the correct queue and set the appropriate bit.  If no
1128          * lower priority (i.e. better) processes are in the queue then
1129          * we want a reschedule, calculate the best cpu for the job.
1130          *
1131          * Always run reschedules on the LWPs original cpu.
1132          */
1133         TAILQ_INSERT_TAIL(q, lp, lwp_procq);
1134         *which |= 1 << pri;
1135 }
1136
1137 #ifdef SMP
1138
1139 /*
1140  * For SMP systems a user scheduler helper thread is created for each
1141  * cpu and is used to allow one cpu to wakeup another for the purposes of
1142  * scheduling userland threads from setrunqueue().
1143  *
1144  * UP systems do not need the helper since there is only one cpu.
1145  *
1146  * We can't use the idle thread for this because we might block.
1147  * Additionally, doing things this way allows us to HLT idle cpus
1148  * on MP systems.
1149  *
1150  * MPSAFE
1151  */
1152 static void
1153 sched_thread(void *dummy)
1154 {
1155     globaldata_t gd;
1156     bsd4_pcpu_t  dd;
1157     struct lwp *nlp;
1158     cpumask_t mask;
1159     int cpuid;
1160 #ifdef SMP
1161     cpumask_t tmpmask;
1162     int tmpid;
1163 #endif
1164
1165     gd = mycpu;
1166     cpuid = gd->gd_cpuid;       /* doesn't change */
1167     mask = gd->gd_cpumask;      /* doesn't change */
1168     dd = &bsd4_pcpu[cpuid];
1169
1170     /*
1171      * Since we are woken up only when no user processes are scheduled
1172      * on a cpu, we can run at an ultra low priority.
1173      */
1174     lwkt_setpri_self(TDPRI_USER_SCHEDULER);
1175
1176     for (;;) {
1177         /*
1178          * We use the LWKT deschedule-interlock trick to avoid racing
1179          * bsd4_rdyprocmask.  This means we cannot block through to the
1180          * manual lwkt_switch() call we make below.
1181          */
1182         crit_enter_gd(gd);
1183         lwkt_deschedule_self(gd->gd_curthread);
1184         spin_lock(&bsd4_spin);
1185         atomic_set_cpumask(&bsd4_rdyprocmask, mask);
1186
1187         clear_user_resched();   /* This satisfied the reschedule request */
1188         dd->rrcount = 0;        /* Reset the round-robin counter */
1189
1190         if ((bsd4_curprocmask & mask) == 0) {
1191                 /*
1192                  * No thread is currently scheduled.
1193                  */
1194                 KKASSERT(dd->uschedcp == NULL);
1195                 if ((nlp = chooseproc_locked(NULL)) != NULL) {
1196                         atomic_set_cpumask(&bsd4_curprocmask, mask);
1197                         dd->upri = nlp->lwp_priority;
1198                         dd->uschedcp = nlp;
1199                         spin_unlock(&bsd4_spin);
1200                         lwkt_acquire(nlp->lwp_thread);
1201                         lwkt_schedule(nlp->lwp_thread);
1202                 } else {
1203                         spin_unlock(&bsd4_spin);
1204                 }
1205         } else if (bsd4_runqcount) {
1206                 if ((nlp = chooseproc_locked(dd->uschedcp)) != NULL) {
1207                         dd->upri = nlp->lwp_priority;
1208                         dd->uschedcp = nlp;
1209                         spin_unlock(&bsd4_spin);
1210                         lwkt_acquire(nlp->lwp_thread);
1211                         lwkt_schedule(nlp->lwp_thread);
1212                 } else {
1213                         /*
1214                          * CHAINING CONDITION TRAIN
1215                          *
1216                          * We could not deal with the scheduler wakeup
1217                          * request on this cpu, locate a ready scheduler
1218                          * with no current lp assignment and chain to it.
1219                          *
1220                          * This ensures that a wakeup race which fails due
1221                          * to priority test does not leave other unscheduled
1222                          * cpus idle when the runqueue is not empty.
1223                          */
1224                         tmpmask = ~bsd4_curprocmask & bsd4_rdyprocmask &
1225                                   smp_active_mask;
1226                         if (tmpmask) {
1227                                 tmpid = BSFCPUMASK(tmpmask);
1228                                 gd = globaldata_find(cpuid);
1229                                 dd = &bsd4_pcpu[cpuid];
1230                                 atomic_clear_cpumask(&bsd4_rdyprocmask,
1231                                                      CPUMASK(tmpid));
1232                                 spin_unlock(&bsd4_spin);
1233                                 lwkt_schedule(&dd->helper_thread);
1234                         } else {
1235                                 spin_unlock(&bsd4_spin);
1236                         }
1237                 }
1238         } else {
1239                 /*
1240                  * The runq is empty.
1241                  */
1242                 spin_unlock(&bsd4_spin);
1243         }
1244         crit_exit_gd(gd);
1245         lwkt_switch();
1246     }
1247 }
1248
1249 /*
1250  * Setup our scheduler helpers.  Note that curprocmask bit 0 has already
1251  * been cleared by rqinit() and we should not mess with it further.
1252  */
1253 static void
1254 sched_thread_cpu_init(void)
1255 {
1256     int i;
1257
1258     if (bootverbose)
1259         kprintf("start scheduler helpers on cpus:");
1260
1261     for (i = 0; i < ncpus; ++i) {
1262         bsd4_pcpu_t dd = &bsd4_pcpu[i];
1263         cpumask_t mask = CPUMASK(i);
1264
1265         if ((mask & smp_active_mask) == 0)
1266             continue;
1267
1268         if (bootverbose)
1269             kprintf(" %d", i);
1270
1271         lwkt_create(sched_thread, NULL, NULL, &dd->helper_thread,
1272                     TDF_STOPREQ, i, "usched %d", i);
1273
1274         /*
1275          * Allow user scheduling on the target cpu.  cpu #0 has already
1276          * been enabled in rqinit().
1277          */
1278         if (i)
1279             atomic_clear_cpumask(&bsd4_curprocmask, mask);
1280         atomic_set_cpumask(&bsd4_rdyprocmask, mask);
1281         dd->upri = PRIBASE_NULL;
1282     }
1283     if (bootverbose)
1284         kprintf("\n");
1285 }
1286 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND,
1287         sched_thread_cpu_init, NULL)
1288
1289 #endif
1290