2 * Copyright (c) 2012 The DragonFly Project. All rights reserved.
3 * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org>. All rights reserved.
5 * This code is derived from software contributed to The DragonFly Project
6 * by Matthew Dillon <dillon@backplane.com>,
7 * by Mihai Carabas <mihai.carabas@gmail.com>
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in
18 * the documentation and/or other materials provided with the
20 * 3. Neither the name of The DragonFly Project nor the names of its
21 * contributors may be used to endorse or promote products derived
22 * from this software without specific, prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
27 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
28 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
29 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
30 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
32 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
33 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
34 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 #include <sys/param.h>
38 #include <sys/systm.h>
39 #include <sys/kernel.h>
41 #include <sys/queue.h>
43 #include <sys/rtprio.h>
45 #include <sys/sysctl.h>
46 #include <sys/resourcevar.h>
47 #include <sys/spinlock.h>
48 #include <sys/cpu_topology.h>
49 #include <sys/thread2.h>
50 #include <sys/spinlock2.h>
51 #include <sys/mplock2.h>
55 #include <machine/cpu.h>
56 #include <machine/smp.h>
59 * Priorities. Note that with 32 run queues per scheduler each queue
60 * represents four priority levels.
66 #define PRIMASK (MAXPRI - 1)
67 #define PRIBASE_REALTIME 0
68 #define PRIBASE_NORMAL MAXPRI
69 #define PRIBASE_IDLE (MAXPRI * 2)
70 #define PRIBASE_THREAD (MAXPRI * 3)
71 #define PRIBASE_NULL (MAXPRI * 4)
73 #define NQS 32 /* 32 run queues. */
74 #define PPQ (MAXPRI / NQS) /* priorities per queue */
75 #define PPQMASK (PPQ - 1)
78 * NICEPPQ - number of nice units per priority queue
79 * ESTCPUPPQ - number of estcpu units per priority queue
80 * ESTCPUMAX - number of estcpu units
84 #define ESTCPUMAX (ESTCPUPPQ * NQS)
85 #define BATCHMAX (ESTCPUFREQ * 30)
86 #define PRIO_RANGE (PRIO_MAX - PRIO_MIN + 1)
88 #define ESTCPULIM(v) min((v), ESTCPUMAX)
92 #define lwp_priority lwp_usdata.dfly.priority
93 #define lwp_forked lwp_usdata.dfly.forked
94 #define lwp_rqindex lwp_usdata.dfly.rqindex
95 #define lwp_estcpu lwp_usdata.dfly.estcpu
96 #define lwp_batch lwp_usdata.dfly.batch
97 #define lwp_rqtype lwp_usdata.dfly.rqtype
98 #define lwp_qcpu lwp_usdata.dfly.qcpu
100 struct usched_dfly_pcpu {
101 struct spinlock spin;
102 struct thread helper_thread;
107 struct lwp *uschedcp;
108 struct rq queues[NQS];
109 struct rq rtqueues[NQS];
110 struct rq idqueues[NQS];
112 u_int32_t rtqueuebits;
113 u_int32_t idqueuebits;
122 typedef struct usched_dfly_pcpu *dfly_pcpu_t;
124 static void dfly_acquire_curproc(struct lwp *lp);
125 static void dfly_release_curproc(struct lwp *lp);
126 static void dfly_select_curproc(globaldata_t gd);
127 static void dfly_setrunqueue(struct lwp *lp);
128 static void dfly_setrunqueue_dd(dfly_pcpu_t rdd, struct lwp *lp);
129 static void dfly_schedulerclock(struct lwp *lp, sysclock_t period,
131 static void dfly_recalculate_estcpu(struct lwp *lp);
132 static void dfly_resetpriority(struct lwp *lp);
133 static void dfly_forking(struct lwp *plp, struct lwp *lp);
134 static void dfly_exiting(struct lwp *lp, struct proc *);
135 static void dfly_uload_update(struct lwp *lp);
136 static void dfly_yield(struct lwp *lp);
138 static void dfly_changeqcpu_locked(struct lwp *lp,
139 dfly_pcpu_t dd, dfly_pcpu_t rdd);
140 static dfly_pcpu_t dfly_choose_best_queue(struct lwp *lp);
141 static dfly_pcpu_t dfly_choose_worst_queue(dfly_pcpu_t dd);
142 static dfly_pcpu_t dfly_choose_queue_simple(dfly_pcpu_t dd, struct lwp *lp);
146 static void dfly_need_user_resched_remote(void *dummy);
148 static struct lwp *dfly_chooseproc_locked(dfly_pcpu_t rdd, dfly_pcpu_t dd,
149 struct lwp *chklp, int worst);
150 static void dfly_remrunqueue_locked(dfly_pcpu_t dd, struct lwp *lp);
151 static void dfly_setrunqueue_locked(dfly_pcpu_t dd, struct lwp *lp);
153 struct usched usched_dfly = {
155 "dfly", "Original DragonFly Scheduler",
156 NULL, /* default registration */
157 NULL, /* default deregistration */
158 dfly_acquire_curproc,
159 dfly_release_curproc,
162 dfly_recalculate_estcpu,
167 NULL, /* setcpumask not supported */
172 * We have NQS (32) run queues per scheduling class. For the normal
173 * class, there are 128 priorities scaled onto these 32 queues. New
174 * processes are added to the last entry in each queue, and processes
175 * are selected for running by taking them from the head and maintaining
176 * a simple FIFO arrangement. Realtime and Idle priority processes have
177 * and explicit 0-31 priority which maps directly onto their class queue
178 * index. When a queue has something in it, the corresponding bit is
179 * set in the queuebits variable, allowing a single read to determine
180 * the state of all 32 queues and then a ffs() to find the first busy
183 static cpumask_t dfly_curprocmask = -1; /* currently running a user process */
184 static cpumask_t dfly_rdyprocmask; /* ready to accept a user process */
186 static volatile int dfly_scancpu;
188 static struct usched_dfly_pcpu dfly_pcpu[MAXCPU];
189 static struct sysctl_ctx_list usched_dfly_sysctl_ctx;
190 static struct sysctl_oid *usched_dfly_sysctl_tree;
192 /* Debug info exposed through debug.* sysctl */
194 static int usched_dfly_debug = -1;
195 SYSCTL_INT(_debug, OID_AUTO, dfly_scdebug, CTLFLAG_RW,
196 &usched_dfly_debug, 0,
197 "Print debug information for this pid");
199 static int usched_dfly_pid_debug = -1;
200 SYSCTL_INT(_debug, OID_AUTO, dfly_pid_debug, CTLFLAG_RW,
201 &usched_dfly_pid_debug, 0,
202 "Print KTR debug information for this pid");
204 static int usched_dfly_chooser = 0;
205 SYSCTL_INT(_debug, OID_AUTO, dfly_chooser, CTLFLAG_RW,
206 &usched_dfly_chooser, 0,
207 "Print KTR debug information for this pid");
210 * Tunning usched_dfly - configurable through kern.usched_dfly.
212 * weight1 - Tries to keep threads on their current cpu. If you
213 * make this value too large the scheduler will not be
214 * able to load-balance large loads.
216 * weight2 - If non-zero, detects thread pairs undergoing synchronous
217 * communications and tries to move them closer together.
218 * Behavior is adjusted by bit 4 of features (0x10).
220 * WARNING! Weight2 is a ridiculously sensitive parameter,
221 * a small value is recommended.
223 * weight3 - Weighting based on the number of recently runnable threads
224 * on the userland scheduling queue (ignoring their loads).
225 * A nominal value here prevents high-priority (low-load)
226 * threads from accumulating on one cpu core when other
227 * cores are available.
229 * This value should be left fairly small relative to weight1
232 * weight4 - Weighting based on other cpu queues being available
233 * or running processes with higher lwp_priority's.
235 * This allows a thread to migrate to another nearby cpu if it
236 * is unable to run on the current cpu based on the other cpu
237 * being idle or running a lower priority (higher lwp_priority)
238 * thread. This value should be large enough to override weight1
240 * features - These flags can be set or cleared to enable or disable various
243 * 0x01 Enable idle-cpu pulling (default)
244 * 0x02 Enable proactive pushing (default)
245 * 0x04 Enable rebalancing rover (default)
246 * 0x08 Enable more proactive pushing (default)
247 * 0x10 (flip weight2 limit on same cpu) (default)
248 * 0x20 choose best cpu for forked process
249 * 0x40 choose current cpu for forked process
250 * 0x80 choose random cpu for forked process (default)
253 static int usched_dfly_smt = 0;
254 static int usched_dfly_cache_coherent = 0;
255 static int usched_dfly_weight1 = 30; /* keep thread on current cpu */
256 static int usched_dfly_weight2 = 15; /* synchronous peer's current cpu */
257 static int usched_dfly_weight3 = 10; /* number of threads on queue */
258 static int usched_dfly_weight4 = 50; /* availability of idle cores */
259 static int usched_dfly_features = 0x8F; /* allow pulls */
261 static int usched_dfly_rrinterval = (ESTCPUFREQ + 9) / 10;
262 static int usched_dfly_decay = 8;
263 static int usched_dfly_batch_time = 10;
265 /* KTR debug printings */
267 KTR_INFO_MASTER(usched);
269 #if !defined(KTR_USCHED_DFLY)
270 #define KTR_USCHED_DFLY KTR_ALL
273 KTR_INFO(KTR_USCHED_DFLY, usched, chooseproc, 0,
274 "USCHED_DFLY(chooseproc: pid %d, old_cpuid %d, curr_cpuid %d)",
275 pid_t pid, int old_cpuid, int curr);
278 * This function is called when the kernel intends to return to userland.
279 * It is responsible for making the thread the current designated userland
280 * thread for this cpu, blocking if necessary.
282 * The kernel has already depressed our LWKT priority so we must not switch
283 * until we have either assigned or disposed of the thread.
285 * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE
286 * TO ANOTHER CPU! Because most of the kernel assumes that no migration will
287 * occur, this function is called only under very controlled circumstances.
290 dfly_acquire_curproc(struct lwp *lp)
301 * Make sure we aren't sitting on a tsleep queue.
304 crit_enter_quick(td);
305 if (td->td_flags & TDF_TSLEEPQ)
307 dfly_recalculate_estcpu(lp);
310 dd = &dfly_pcpu[gd->gd_cpuid];
313 * Process any pending interrupts/ipi's, then handle reschedule
314 * requests. dfly_release_curproc() will try to assign a new
315 * uschedcp that isn't us and otherwise NULL it out.
318 if (user_resched_wanted()) {
319 if (dd->uschedcp == lp)
321 clear_user_resched();
322 dfly_release_curproc(lp);
326 * Loop until we are the current user thread.
328 * NOTE: dd spinlock not held at top of loop.
330 if (dd->uschedcp == lp)
333 while (dd->uschedcp != lp) {
336 spin_lock(&dd->spin);
339 * We are not or are no longer the current lwp and a forced
340 * reschedule was requested. Figure out the best cpu to
341 * run on (our current cpu will be given significant weight).
343 * (if a reschedule was not requested we want to move this
344 * step after the uschedcp tests).
348 (usched_dfly_features & 0x08) &&
349 (rdd = dfly_choose_best_queue(lp)) != dd) {
350 dfly_changeqcpu_locked(lp, dd, rdd);
351 spin_unlock(&dd->spin);
352 lwkt_deschedule(lp->lwp_thread);
353 dfly_setrunqueue_dd(rdd, lp);
356 dd = &dfly_pcpu[gd->gd_cpuid];
362 * Either no reschedule was requested or the best queue was
363 * dd, and no current process has been selected. We can
364 * trivially become the current lwp on the current cpu.
366 if (dd->uschedcp == NULL) {
367 atomic_set_cpumask(&dfly_curprocmask, gd->gd_cpumask);
369 dd->upri = lp->lwp_priority;
370 KKASSERT(lp->lwp_qcpu == dd->cpuid);
371 spin_unlock(&dd->spin);
376 * Can we steal the current designated user thread?
378 * If we do the other thread will stall when it tries to
379 * return to userland, possibly rescheduling elsewhere.
381 * It is important to do a masked test to avoid the edge
382 * case where two near-equal-priority threads are constantly
383 * interrupting each other.
386 (dd->upri & ~PPQMASK) >
387 (lp->lwp_priority & ~PPQMASK)) {
389 dd->upri = lp->lwp_priority;
390 KKASSERT(lp->lwp_qcpu == dd->cpuid);
391 spin_unlock(&dd->spin);
397 * We are not the current lwp, figure out the best cpu
398 * to run on (our current cpu will be given significant
399 * weight). Loop on cpu change.
401 if ((usched_dfly_features & 0x02) &&
402 force_resched == 0 &&
403 (rdd = dfly_choose_best_queue(lp)) != dd) {
404 dfly_changeqcpu_locked(lp, dd, rdd);
405 spin_unlock(&dd->spin);
406 lwkt_deschedule(lp->lwp_thread);
407 dfly_setrunqueue_dd(rdd, lp);
410 dd = &dfly_pcpu[gd->gd_cpuid];
416 * We cannot become the current lwp, place the lp on the
417 * run-queue of this or another cpu and deschedule ourselves.
419 * When we are reactivated we will have another chance.
421 * Reload after a switch or setrunqueue/switch possibly
422 * moved us to another cpu.
424 spin_unlock(&dd->spin);
425 lwkt_deschedule(lp->lwp_thread);
426 dfly_setrunqueue_dd(dd, lp);
429 dd = &dfly_pcpu[gd->gd_cpuid];
433 * Make sure upri is synchronized, then yield to LWKT threads as
434 * needed before returning. This could result in another reschedule.
439 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
443 * DFLY_RELEASE_CURPROC
445 * This routine detaches the current thread from the userland scheduler,
446 * usually because the thread needs to run or block in the kernel (at
447 * kernel priority) for a while.
449 * This routine is also responsible for selecting a new thread to
450 * make the current thread.
452 * NOTE: This implementation differs from the dummy example in that
453 * dfly_select_curproc() is able to select the current process, whereas
454 * dummy_select_curproc() is not able to select the current process.
455 * This means we have to NULL out uschedcp.
457 * Additionally, note that we may already be on a run queue if releasing
458 * via the lwkt_switch() in dfly_setrunqueue().
461 dfly_release_curproc(struct lwp *lp)
463 globaldata_t gd = mycpu;
464 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
467 * Make sure td_wakefromcpu is defaulted. This will be overwritten
470 if (dd->uschedcp == lp) {
471 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
472 spin_lock(&dd->spin);
473 if (dd->uschedcp == lp) {
474 dd->uschedcp = NULL; /* don't let lp be selected */
475 dd->upri = PRIBASE_NULL;
476 atomic_clear_cpumask(&dfly_curprocmask, gd->gd_cpumask);
477 spin_unlock(&dd->spin);
478 dfly_select_curproc(gd);
480 spin_unlock(&dd->spin);
486 * DFLY_SELECT_CURPROC
488 * Select a new current process for this cpu and clear any pending user
489 * reschedule request. The cpu currently has no current process.
491 * This routine is also responsible for equal-priority round-robining,
492 * typically triggered from dfly_schedulerclock(). In our dummy example
493 * all the 'user' threads are LWKT scheduled all at once and we just
494 * call lwkt_switch().
496 * The calling process is not on the queue and cannot be selected.
500 dfly_select_curproc(globaldata_t gd)
502 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
504 int cpuid = gd->gd_cpuid;
508 spin_lock(&dd->spin);
509 nlp = dfly_chooseproc_locked(dd, dd, dd->uschedcp, 0);
512 atomic_set_cpumask(&dfly_curprocmask, CPUMASK(cpuid));
513 dd->upri = nlp->lwp_priority;
515 dd->rrcount = 0; /* reset round robin */
516 spin_unlock(&dd->spin);
518 lwkt_acquire(nlp->lwp_thread);
520 lwkt_schedule(nlp->lwp_thread);
522 spin_unlock(&dd->spin);
528 * Place the specified lwp on the user scheduler's run queue. This routine
529 * must be called with the thread descheduled. The lwp must be runnable.
530 * It must not be possible for anyone else to explicitly schedule this thread.
532 * The thread may be the current thread as a special case.
535 dfly_setrunqueue(struct lwp *lp)
541 * First validate the process LWKT state.
543 KASSERT(lp->lwp_stat == LSRUN, ("setrunqueue: lwp not LSRUN"));
544 KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0,
545 ("lwp %d/%d already on runq! flag %08x/%08x", lp->lwp_proc->p_pid,
546 lp->lwp_tid, lp->lwp_proc->p_flags, lp->lwp_flags));
547 KKASSERT((lp->lwp_thread->td_flags & TDF_RUNQ) == 0);
550 * NOTE: dd/rdd do not necessarily represent the current cpu.
551 * Instead they may represent the cpu the thread was last
552 * scheduled on or inherited by its parent.
554 dd = &dfly_pcpu[lp->lwp_qcpu];
558 * This process is not supposed to be scheduled anywhere or assigned
559 * as the current process anywhere. Assert the condition.
561 KKASSERT(rdd->uschedcp != lp);
565 * If we are not SMP we do not have a scheduler helper to kick
566 * and must directly activate the process if none are scheduled.
568 * This is really only an issue when bootstrapping init since
569 * the caller in all other cases will be a user process, and
570 * even if released (rdd->uschedcp == NULL), that process will
571 * kickstart the scheduler when it returns to user mode from
574 * NOTE: On SMP we can't just set some other cpu's uschedcp.
576 if (rdd->uschedcp == NULL) {
577 spin_lock(&rdd->spin);
578 if (rdd->uschedcp == NULL) {
579 atomic_set_cpumask(&dfly_curprocmask, 1);
581 rdd->upri = lp->lwp_priority;
582 spin_unlock(&rdd->spin);
583 lwkt_schedule(lp->lwp_thread);
586 spin_unlock(&rdd->spin);
592 * Ok, we have to setrunqueue some target cpu and request a reschedule
595 * We have to choose the best target cpu. It might not be the current
596 * target even if the current cpu has no running user thread (for
597 * example, because the current cpu might be a hyperthread and its
598 * sibling has a thread assigned).
600 * If we just forked it is most optimal to run the child on the same
601 * cpu just in case the parent decides to wait for it (thus getting
602 * off that cpu). As long as there is nothing else runnable on the
603 * cpu, that is. If we did this unconditionally a parent forking
604 * multiple children before waiting (e.g. make -j N) leaves other
605 * cpus idle that could be working.
607 if (lp->lwp_forked) {
609 if (usched_dfly_features & 0x20)
610 rdd = dfly_choose_best_queue(lp);
611 else if (usched_dfly_features & 0x40)
612 rdd = &dfly_pcpu[lp->lwp_qcpu];
613 else if (usched_dfly_features & 0x80)
614 rdd = dfly_choose_queue_simple(rdd, lp);
615 else if (dfly_pcpu[lp->lwp_qcpu].runqcount)
616 rdd = dfly_choose_best_queue(lp);
618 rdd = &dfly_pcpu[lp->lwp_qcpu];
620 rdd = dfly_choose_best_queue(lp);
621 /* rdd = &dfly_pcpu[lp->lwp_qcpu]; */
623 if (lp->lwp_qcpu != rdd->cpuid) {
624 spin_lock(&dd->spin);
625 dfly_changeqcpu_locked(lp, dd, rdd);
626 spin_unlock(&dd->spin);
629 dfly_setrunqueue_dd(rdd, lp);
635 * Change qcpu to rdd->cpuid. The dd the lp is CURRENTLY on must be
636 * spin-locked on-call. rdd does not have to be.
639 dfly_changeqcpu_locked(struct lwp *lp, dfly_pcpu_t dd, dfly_pcpu_t rdd)
641 if (lp->lwp_qcpu != rdd->cpuid) {
642 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
643 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
644 atomic_add_int(&dd->uload,
645 -((lp->lwp_priority & ~PPQMASK) & PRIMASK));
646 atomic_add_int(&dd->ucount, -1);
648 lp->lwp_qcpu = rdd->cpuid;
655 * Place lp on rdd's runqueue. Nothing is locked on call. This function
656 * also performs all necessary ancillary notification actions.
659 dfly_setrunqueue_dd(dfly_pcpu_t rdd, struct lwp *lp)
665 * We might be moving the lp to another cpu's run queue, and once
666 * on the runqueue (even if it is our cpu's), another cpu can rip
669 * TDF_MIGRATING might already be set if this is part of a
670 * remrunqueue+setrunqueue sequence.
672 if ((lp->lwp_thread->td_flags & TDF_MIGRATING) == 0)
673 lwkt_giveaway(lp->lwp_thread);
675 rgd = globaldata_find(rdd->cpuid);
678 * We lose control of the lp the moment we release the spinlock
679 * after having placed it on the queue. i.e. another cpu could pick
680 * it up, or it could exit, or its priority could be further
681 * adjusted, or something like that.
683 * WARNING! rdd can point to a foreign cpu!
685 spin_lock(&rdd->spin);
686 dfly_setrunqueue_locked(rdd, lp);
689 if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) {
690 spin_unlock(&rdd->spin);
691 if (rdd->uschedcp == NULL) {
692 wakeup_mycpu(&rdd->helper_thread); /* XXX */
698 spin_unlock(&rdd->spin);
701 if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) {
702 spin_unlock(&rdd->spin);
703 lwkt_send_ipiq(rgd, dfly_need_user_resched_remote,
705 } else if (dfly_rdyprocmask & rgd->gd_cpumask) {
706 atomic_clear_cpumask(&dfly_rdyprocmask,
708 spin_unlock(&rdd->spin);
709 wakeup(&rdd->helper_thread);
711 spin_unlock(&rdd->spin);
716 * Request a reschedule if appropriate.
718 spin_lock(&rdd->spin);
719 dfly_setrunqueue_locked(rdd, lp);
720 spin_unlock(&rdd->spin);
721 if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) {
728 * This routine is called from a systimer IPI. It MUST be MP-safe and
729 * the BGL IS NOT HELD ON ENTRY. This routine is called at ESTCPUFREQ on
734 dfly_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp)
736 globaldata_t gd = mycpu;
737 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
740 * Spinlocks also hold a critical section so there should not be
743 KKASSERT(gd->gd_spinlocks_wr == 0);
749 * Do we need to round-robin? We round-robin 10 times a second.
750 * This should only occur for cpu-bound batch processes.
752 if (++dd->rrcount >= usched_dfly_rrinterval) {
753 lp->lwp_thread->td_wakefromcpu = -1;
759 * Adjust estcpu upward using a real time equivalent calculation,
760 * and recalculate lp's priority.
762 lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUMAX / ESTCPUFREQ + 1);
763 dfly_resetpriority(lp);
766 * Rebalance cpus on each scheduler tick. Each cpu in turn will
767 * calculate the worst queue and, if sufficiently loaded, will
768 * pull a process from that queue into our current queue.
770 * To try to avoid always moving the same thread. XXX
773 if ((usched_dfly_features & 0x04) &&
774 ((uint16_t)sched_ticks % ncpus) == gd->gd_cpuid) {
782 * We have to choose the worst thread in the worst queue
783 * because it likely finished its batch on that cpu and is
784 * now waiting for cpu again.
786 rdd = dfly_choose_worst_queue(dd);
788 spin_lock(&dd->spin);
789 if (spin_trylock(&rdd->spin)) {
790 nlp = dfly_chooseproc_locked(rdd, dd, NULL, 1);
791 spin_unlock(&rdd->spin);
793 spin_unlock(&dd->spin);
795 spin_unlock(&dd->spin);
801 /* dd->spin held if nlp != NULL */
804 * Either schedule it or add it to our queue.
807 (nlp->lwp_priority & ~PPQMASK) < (dd->upri & ~PPQMASK)) {
808 atomic_set_cpumask(&dfly_curprocmask, dd->cpumask);
809 dd->upri = nlp->lwp_priority;
811 dd->rrcount = 0; /* reset round robin */
812 spin_unlock(&dd->spin);
813 lwkt_acquire(nlp->lwp_thread);
814 lwkt_schedule(nlp->lwp_thread);
816 dfly_setrunqueue_locked(dd, nlp);
817 spin_unlock(&dd->spin);
824 * Called from acquire and from kern_synch's one-second timer (one of the
825 * callout helper threads) with a critical section held.
827 * Decay p_estcpu based on the number of ticks we haven't been running
828 * and our p_nice. As the load increases each process observes a larger
829 * number of idle ticks (because other processes are running in them).
830 * This observation leads to a larger correction which tends to make the
831 * system more 'batchy'.
833 * Note that no recalculation occurs for a process which sleeps and wakes
834 * up in the same tick. That is, a system doing thousands of context
835 * switches per second will still only do serious estcpu calculations
836 * ESTCPUFREQ times per second.
840 dfly_recalculate_estcpu(struct lwp *lp)
842 globaldata_t gd = mycpu;
843 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
850 * We have to subtract periodic to get the last schedclock
851 * timeout time, otherwise we would get the upcoming timeout.
852 * Keep in mind that a process can migrate between cpus and
853 * while the scheduler clock should be very close, boundary
854 * conditions could lead to a small negative delta.
856 cpbase = gd->gd_schedclock.time - gd->gd_schedclock.periodic;
858 if (lp->lwp_slptime > 1) {
860 * Too much time has passed, do a coarse correction.
862 lp->lwp_estcpu = lp->lwp_estcpu >> 1;
863 dfly_resetpriority(lp);
864 lp->lwp_cpbase = cpbase;
866 lp->lwp_batch -= ESTCPUFREQ;
867 if (lp->lwp_batch < 0)
869 } else if (lp->lwp_cpbase != cpbase) {
871 * Adjust estcpu if we are in a different tick. Don't waste
872 * time if we are in the same tick.
874 * First calculate the number of ticks in the measurement
875 * interval. The ttlticks calculation can wind up 0 due to
876 * a bug in the handling of lwp_slptime (as yet not found),
877 * so make sure we do not get a divide by 0 panic.
879 ttlticks = (cpbase - lp->lwp_cpbase) /
880 gd->gd_schedclock.periodic;
883 lp->lwp_cpbase = cpbase;
887 updatepcpu(lp, lp->lwp_cpticks, ttlticks);
890 * Calculate the percentage of one cpu used factoring in ncpus
891 * and the load and adjust estcpu. Handle degenerate cases
892 * by adding 1 to runqcount.
894 * estcpu is scaled by ESTCPUMAX.
896 * runqcount is the excess number of user processes
897 * that cannot be immediately scheduled to cpus. We want
898 * to count these as running to avoid range compression
899 * in the base calculation (which is the actual percentage
902 estcpu = (lp->lwp_cpticks * ESTCPUMAX) *
903 (dd->runqcount + ncpus) / (ncpus * ttlticks);
906 * If estcpu is > 50% we become more batch-like
907 * If estcpu is <= 50% we become less batch-like
909 * It takes 30 cpu seconds to traverse the entire range.
911 if (estcpu > ESTCPUMAX / 2) {
912 lp->lwp_batch += ttlticks;
913 if (lp->lwp_batch > BATCHMAX)
914 lp->lwp_batch = BATCHMAX;
916 lp->lwp_batch -= ttlticks;
917 if (lp->lwp_batch < 0)
921 if (usched_dfly_debug == lp->lwp_proc->p_pid) {
922 kprintf("pid %d lwp %p estcpu %3d %3d bat %d cp %d/%d",
923 lp->lwp_proc->p_pid, lp,
924 estcpu, lp->lwp_estcpu,
926 lp->lwp_cpticks, ttlticks);
930 * Adjust lp->lwp_esetcpu. The decay factor determines how
931 * quickly lwp_estcpu collapses to its realtime calculation.
932 * A slower collapse gives us a more accurate number but
933 * can cause a cpu hog to eat too much cpu before the
934 * scheduler decides to downgrade it.
936 * NOTE: p_nice is accounted for in dfly_resetpriority(),
937 * and not here, but we must still ensure that a
938 * cpu-bound nice -20 process does not completely
939 * override a cpu-bound nice +20 process.
941 * NOTE: We must use ESTCPULIM() here to deal with any
944 decay_factor = usched_dfly_decay;
945 if (decay_factor < 1)
947 if (decay_factor > 1024)
950 lp->lwp_estcpu = ESTCPULIM(
951 (lp->lwp_estcpu * decay_factor + estcpu) /
954 if (usched_dfly_debug == lp->lwp_proc->p_pid)
955 kprintf(" finalestcpu %d\n", lp->lwp_estcpu);
956 dfly_resetpriority(lp);
957 lp->lwp_cpbase += ttlticks * gd->gd_schedclock.periodic;
963 * Compute the priority of a process when running in user mode.
964 * Arrange to reschedule if the resulting priority is better
965 * than that of the current process.
967 * This routine may be called with any process.
969 * This routine is called by fork1() for initial setup with the process
970 * of the run queue, and also may be called normally with the process on or
974 dfly_resetpriority(struct lwp *lp)
986 * Lock the scheduler (lp) belongs to. This can be on a different
987 * cpu. Handle races. This loop breaks out with the appropriate
993 rdd = &dfly_pcpu[rcpu];
994 spin_lock(&rdd->spin);
995 if (rcpu == lp->lwp_qcpu)
997 spin_unlock(&rdd->spin);
1001 * Calculate the new priority and queue type
1003 newrqtype = lp->lwp_rtprio.type;
1006 case RTP_PRIO_REALTIME:
1008 newpriority = PRIBASE_REALTIME +
1009 (lp->lwp_rtprio.prio & PRIMASK);
1011 case RTP_PRIO_NORMAL:
1013 * Detune estcpu based on batchiness. lwp_batch ranges
1014 * from 0 to BATCHMAX. Limit estcpu for the sake of
1015 * the priority calculation to between 50% and 100%.
1017 estcpu = lp->lwp_estcpu * (lp->lwp_batch + BATCHMAX) /
1021 * p_nice piece Adds (0-40) * 2 0-80
1022 * estcpu Adds 16384 * 4 / 512 0-128
1024 newpriority = (lp->lwp_proc->p_nice - PRIO_MIN) * PPQ / NICEPPQ;
1025 newpriority += estcpu * PPQ / ESTCPUPPQ;
1026 newpriority = newpriority * MAXPRI / (PRIO_RANGE * PPQ /
1027 NICEPPQ + ESTCPUMAX * PPQ / ESTCPUPPQ);
1028 newpriority = PRIBASE_NORMAL + (newpriority & PRIMASK);
1031 newpriority = PRIBASE_IDLE + (lp->lwp_rtprio.prio & PRIMASK);
1033 case RTP_PRIO_THREAD:
1034 newpriority = PRIBASE_THREAD + (lp->lwp_rtprio.prio & PRIMASK);
1037 panic("Bad RTP_PRIO %d", newrqtype);
1042 * The newpriority incorporates the queue type so do a simple masked
1043 * check to determine if the process has moved to another queue. If
1044 * it has, and it is currently on a run queue, then move it.
1046 * Since uload is ~PPQMASK masked, no modifications are necessary if
1047 * we end up in the same run queue.
1049 if ((lp->lwp_priority ^ newpriority) & ~PPQMASK) {
1053 * uload can change, calculate the adjustment to reduce
1054 * edge cases since choosers scan the cpu topology without
1057 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1059 -((lp->lwp_priority & ~PPQMASK) & PRIMASK) +
1060 ((newpriority & ~PPQMASK) & PRIMASK);
1061 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].uload,
1063 /* no change in ucount */
1065 if (lp->lwp_mpflags & LWP_MP_ONRUNQ) {
1066 dfly_remrunqueue_locked(rdd, lp);
1067 lp->lwp_priority = newpriority;
1068 lp->lwp_rqtype = newrqtype;
1069 lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ;
1070 dfly_setrunqueue_locked(rdd, lp);
1073 lp->lwp_priority = newpriority;
1074 lp->lwp_rqtype = newrqtype;
1075 lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ;
1080 * In the same PPQ, uload cannot change.
1082 lp->lwp_priority = newpriority;
1088 * Determine if we need to reschedule the target cpu. This only
1089 * occurs if the LWP is already on a scheduler queue, which means
1090 * that idle cpu notification has already occured. At most we
1091 * need only issue a need_user_resched() on the appropriate cpu.
1093 * The LWP may be owned by a CPU different from the current one,
1094 * in which case dd->uschedcp may be modified without an MP lock
1095 * or a spinlock held. The worst that happens is that the code
1096 * below causes a spurious need_user_resched() on the target CPU
1097 * and dd->pri to be wrong for a short period of time, both of
1098 * which are harmless.
1100 * If checkpri is 0 we are adjusting the priority of the current
1101 * process, possibly higher (less desireable), so ignore the upri
1102 * check which will fail in that case.
1105 if ((dfly_rdyprocmask & CPUMASK(rcpu)) &&
1107 (rdd->upri & ~PRIMASK) > (lp->lwp_priority & ~PRIMASK))) {
1109 if (rcpu == mycpu->gd_cpuid) {
1110 spin_unlock(&rdd->spin);
1111 need_user_resched();
1113 atomic_clear_cpumask(&dfly_rdyprocmask,
1115 spin_unlock(&rdd->spin);
1116 lwkt_send_ipiq(globaldata_find(rcpu),
1117 dfly_need_user_resched_remote,
1121 spin_unlock(&rdd->spin);
1122 need_user_resched();
1125 spin_unlock(&rdd->spin);
1128 spin_unlock(&rdd->spin);
1135 dfly_yield(struct lwp *lp)
1138 /* FUTURE (or something similar) */
1139 switch(lp->lwp_rqtype) {
1140 case RTP_PRIO_NORMAL:
1141 lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUINCR);
1147 need_user_resched();
1151 * Called from fork1() when a new child process is being created.
1153 * Give the child process an initial estcpu that is more batch then
1154 * its parent and dock the parent for the fork (but do not
1155 * reschedule the parent). This comprises the main part of our batch
1156 * detection heuristic for both parallel forking and sequential execs.
1158 * XXX lwp should be "spawning" instead of "forking"
1161 dfly_forking(struct lwp *plp, struct lwp *lp)
1164 * Put the child 4 queue slots (out of 32) higher than the parent
1165 * (less desireable than the parent).
1167 lp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ * 4);
1171 * The batch status of children always starts out centerline
1172 * and will inch-up or inch-down as appropriate. It takes roughly
1173 * ~15 seconds of >50% cpu to hit the limit.
1175 lp->lwp_batch = BATCHMAX / 2;
1178 * Dock the parent a cost for the fork, protecting us from fork
1179 * bombs. If the parent is forking quickly make the child more
1182 plp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ / 16);
1186 * Called when a lwp is being removed from this scheduler, typically
1187 * during lwp_exit(). We have to clean out any ULOAD accounting before
1188 * we can let the lp go. The dd->spin lock is not needed for uload
1191 * Scheduler dequeueing has already occurred, no further action in that
1195 dfly_exiting(struct lwp *lp, struct proc *child_proc)
1197 dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu];
1199 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1200 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
1201 atomic_add_int(&dd->uload,
1202 -((lp->lwp_priority & ~PPQMASK) & PRIMASK));
1203 atomic_add_int(&dd->ucount, -1);
1208 * This function cannot block in any way, but spinlocks are ok.
1210 * Update the uload based on the state of the thread (whether it is going
1211 * to sleep or running again). The uload is meant to be a longer-term
1212 * load and not an instantanious load.
1215 dfly_uload_update(struct lwp *lp)
1217 dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu];
1219 if (lp->lwp_thread->td_flags & TDF_RUNQ) {
1220 if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) {
1221 spin_lock(&dd->spin);
1222 if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) {
1223 atomic_set_int(&lp->lwp_mpflags,
1225 atomic_add_int(&dd->uload,
1226 ((lp->lwp_priority & ~PPQMASK) & PRIMASK));
1227 atomic_add_int(&dd->ucount, 1);
1229 spin_unlock(&dd->spin);
1231 } else if (lp->lwp_slptime > 0) {
1232 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1233 spin_lock(&dd->spin);
1234 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1235 atomic_clear_int(&lp->lwp_mpflags,
1237 atomic_add_int(&dd->uload,
1238 -((lp->lwp_priority & ~PPQMASK) & PRIMASK));
1239 atomic_add_int(&dd->ucount, -1);
1241 spin_unlock(&dd->spin);
1247 * chooseproc() is called when a cpu needs a user process to LWKT schedule,
1248 * it selects a user process and returns it. If chklp is non-NULL and chklp
1249 * has a better or equal priority then the process that would otherwise be
1250 * chosen, NULL is returned.
1252 * Until we fix the RUNQ code the chklp test has to be strict or we may
1253 * bounce between processes trying to acquire the current process designation.
1255 * Must be called with rdd->spin locked. The spinlock is left intact through
1256 * the entire routine. dd->spin does not have to be locked.
1258 * If worst is non-zero this function finds the worst thread instead of the
1259 * best thread (used by the schedulerclock-based rover).
1263 dfly_chooseproc_locked(dfly_pcpu_t rdd, dfly_pcpu_t dd,
1264 struct lwp *chklp, int worst)
1268 u_int32_t *which, *which2;
1274 rtqbits = rdd->rtqueuebits;
1275 tsqbits = rdd->queuebits;
1276 idqbits = rdd->idqueuebits;
1280 pri = bsrl(idqbits);
1281 q = &rdd->idqueues[pri];
1282 which = &rdd->idqueuebits;
1284 } else if (tsqbits) {
1285 pri = bsrl(tsqbits);
1286 q = &rdd->queues[pri];
1287 which = &rdd->queuebits;
1289 } else if (rtqbits) {
1290 pri = bsrl(rtqbits);
1291 q = &rdd->rtqueues[pri];
1292 which = &rdd->rtqueuebits;
1297 lp = TAILQ_LAST(q, rq);
1300 pri = bsfl(rtqbits);
1301 q = &rdd->rtqueues[pri];
1302 which = &rdd->rtqueuebits;
1304 } else if (tsqbits) {
1305 pri = bsfl(tsqbits);
1306 q = &rdd->queues[pri];
1307 which = &rdd->queuebits;
1309 } else if (idqbits) {
1310 pri = bsfl(idqbits);
1311 q = &rdd->idqueues[pri];
1312 which = &rdd->idqueuebits;
1317 lp = TAILQ_FIRST(q);
1319 KASSERT(lp, ("chooseproc: no lwp on busy queue"));
1322 * If the passed lwp <chklp> is reasonably close to the selected
1323 * lwp <lp>, return NULL (indicating that <chklp> should be kept).
1325 * Note that we must error on the side of <chklp> to avoid bouncing
1326 * between threads in the acquire code.
1329 if (chklp->lwp_priority < lp->lwp_priority + PPQ)
1333 KTR_COND_LOG(usched_chooseproc,
1334 lp->lwp_proc->p_pid == usched_dfly_pid_debug,
1335 lp->lwp_proc->p_pid,
1336 lp->lwp_thread->td_gd->gd_cpuid,
1339 KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) != 0, ("not on runq6!"));
1340 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
1341 TAILQ_REMOVE(q, lp, lwp_procq);
1344 *which &= ~(1 << pri);
1347 * If we are choosing a process from rdd with the intent to
1348 * move it to dd, lwp_qcpu must be adjusted while rdd's spinlock
1352 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1353 atomic_add_int(&rdd->uload,
1354 -((lp->lwp_priority & ~PPQMASK) & PRIMASK));
1355 atomic_add_int(&rdd->ucount, -1);
1357 lp->lwp_qcpu = dd->cpuid;
1358 atomic_add_int(&dd->uload,
1359 ((lp->lwp_priority & ~PPQMASK) & PRIMASK));
1360 atomic_add_int(&dd->ucount, 1);
1361 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
1369 * USED TO PUSH RUNNABLE LWPS TO THE LEAST LOADED CPU.
1371 * Choose a cpu node to schedule lp on, hopefully nearby its current
1374 * We give the current node a modest advantage for obvious reasons.
1376 * We also give the node the thread was woken up FROM a slight advantage
1377 * in order to try to schedule paired threads which synchronize/block waiting
1378 * for each other fairly close to each other. Similarly in a network setting
1379 * this feature will also attempt to place a user process near the kernel
1380 * protocol thread that is feeding it data. THIS IS A CRITICAL PART of the
1381 * algorithm as it heuristically groups synchronizing processes for locality
1382 * of reference in multi-socket systems.
1384 * We check against running processes and give a big advantage if there
1387 * The caller will normally dfly_setrunqueue() lp on the returned queue.
1389 * When the topology is known choose a cpu whos group has, in aggregate,
1390 * has the lowest weighted load.
1394 dfly_choose_best_queue(struct lwp *lp)
1401 dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu];
1411 * When the topology is unknown choose a random cpu that is hopefully
1414 if (dd->cpunode == NULL)
1415 return (dfly_choose_queue_simple(dd, lp));
1420 if ((wakecpu = lp->lwp_thread->td_wakefromcpu) >= 0)
1421 wakemask = dfly_pcpu[wakecpu].cpumask;
1426 * When the topology is known choose a cpu whos group has, in
1427 * aggregate, has the lowest weighted load.
1429 cpup = root_cpu_node;
1434 * Degenerate case super-root
1436 if (cpup->child_node && cpup->child_no == 1) {
1437 cpup = cpup->child_node;
1444 if (cpup->child_node == NULL) {
1445 rdd = &dfly_pcpu[BSFCPUMASK(cpup->members)];
1450 lowest_load = 0x7FFFFFFF;
1452 for (n = 0; n < cpup->child_no; ++n) {
1454 * Accumulate load information for all cpus
1455 * which are members of this node.
1457 cpun = &cpup->child_node[n];
1458 mask = cpun->members & usched_global_cpumask &
1459 smp_active_mask & lp->lwp_cpumask;
1467 cpuid = BSFCPUMASK(mask);
1468 rdd = &dfly_pcpu[cpuid];
1470 load += rdd->ucount * usched_dfly_weight3;
1472 if (rdd->uschedcp == NULL &&
1473 rdd->runqcount == 0) {
1474 load -= usched_dfly_weight4;
1475 } else if (rdd->upri > lp->lwp_priority + PPQ) {
1476 load -= usched_dfly_weight4 / 2;
1478 mask &= ~CPUMASK(cpuid);
1483 * Compensate if the lp is already accounted for in
1484 * the aggregate uload for this mask set. We want
1485 * to calculate the loads as if lp were not present,
1486 * otherwise the calculation is bogus.
1488 if ((lp->lwp_mpflags & LWP_MP_ULOAD) &&
1489 (dd->cpumask & cpun->members)) {
1490 load -= ((lp->lwp_priority & ~PPQMASK) &
1492 load -= usched_dfly_weight3;
1498 * Advantage the cpu group (lp) is already on.
1500 if (cpun->members & dd->cpumask)
1501 load -= usched_dfly_weight1;
1504 * Advantage the cpu group we want to pair (lp) to,
1505 * but don't let it go to the exact same cpu as
1506 * the wakecpu target.
1508 * We do this by checking whether cpun is a
1509 * terminal node or not. All cpun's at the same
1510 * level will either all be terminal or all not
1513 * If it is and we match we disadvantage the load.
1514 * If it is and we don't match we advantage the load.
1516 * Also note that we are effectively disadvantaging
1517 * all-but-one by the same amount, so it won't effect
1518 * the weight1 factor for the all-but-one nodes.
1520 if (cpun->members & wakemask) {
1521 if (cpun->child_node != NULL) {
1523 load -= usched_dfly_weight2;
1525 if (usched_dfly_features & 0x10)
1526 load += usched_dfly_weight2;
1528 load -= usched_dfly_weight2;
1533 * Calculate the best load
1535 if (cpub == NULL || lowest_load > load ||
1536 (lowest_load == load &&
1537 (cpun->members & dd->cpumask))
1545 if (usched_dfly_chooser)
1546 kprintf("lp %02d->%02d %s\n",
1547 lp->lwp_qcpu, rdd->cpuid, lp->lwp_proc->p_comm);
1552 * USED TO PULL RUNNABLE LWPS FROM THE MOST LOADED CPU.
1554 * Choose the worst queue close to dd's cpu node with a non-empty runq
1555 * that is NOT dd. Also require that the moving of the highest-load thread
1556 * from rdd to dd does not cause the uload's to cross each other.
1558 * This is used by the thread chooser when the current cpu's queues are
1559 * empty to steal a thread from another cpu's queue. We want to offload
1560 * the most heavily-loaded queue.
1564 dfly_choose_worst_queue(dfly_pcpu_t dd)
1580 * When the topology is unknown choose a random cpu that is hopefully
1583 if (dd->cpunode == NULL) {
1588 * When the topology is known choose a cpu whos group has, in
1589 * aggregate, has the lowest weighted load.
1591 cpup = root_cpu_node;
1595 * Degenerate case super-root
1597 if (cpup->child_node && cpup->child_no == 1) {
1598 cpup = cpup->child_node;
1605 if (cpup->child_node == NULL) {
1606 rdd = &dfly_pcpu[BSFCPUMASK(cpup->members)];
1613 for (n = 0; n < cpup->child_no; ++n) {
1615 * Accumulate load information for all cpus
1616 * which are members of this node.
1618 cpun = &cpup->child_node[n];
1619 mask = cpun->members & usched_global_cpumask &
1627 cpuid = BSFCPUMASK(mask);
1628 rdd = &dfly_pcpu[cpuid];
1630 load += rdd->ucount * usched_dfly_weight3;
1631 if (rdd->uschedcp == NULL &&
1632 rdd->runqcount == 0 &&
1633 globaldata_find(cpuid)->gd_tdrunqcount == 0
1635 load -= usched_dfly_weight4;
1636 } else if (rdd->upri > dd->upri + PPQ) {
1637 load -= usched_dfly_weight4 / 2;
1639 mask &= ~CPUMASK(cpuid);
1645 * Prefer candidates which are somewhat closer to
1648 if (dd->cpumask & cpun->members)
1649 load += usched_dfly_weight1;
1652 * The best candidate is the one with the worst
1655 if (cpub == NULL || highest_load < load) {
1656 highest_load = load;
1664 * We never return our own node (dd), and only return a remote
1665 * node if it's load is significantly worse than ours (i.e. where
1666 * stealing a thread would be considered reasonable).
1668 * This also helps us avoid breaking paired threads apart which
1669 * can have disastrous effects on performance.
1675 if (rdd->rtqueuebits && hpri < (pri = bsrl(rdd->rtqueuebits)))
1677 if (rdd->queuebits && hpri < (pri = bsrl(rdd->queuebits)))
1679 if (rdd->idqueuebits && hpri < (pri = bsrl(rdd->idqueuebits)))
1682 if (rdd->uload - hpri < dd->uload + hpri)
1689 dfly_choose_queue_simple(dfly_pcpu_t dd, struct lwp *lp)
1697 * Fallback to the original heuristic, select random cpu,
1698 * first checking cpus not currently running a user thread.
1701 cpuid = (dfly_scancpu & 0xFFFF) % ncpus;
1702 mask = ~dfly_curprocmask & dfly_rdyprocmask & lp->lwp_cpumask &
1703 smp_active_mask & usched_global_cpumask;
1706 tmpmask = ~(CPUMASK(cpuid) - 1);
1708 cpuid = BSFCPUMASK(mask & tmpmask);
1710 cpuid = BSFCPUMASK(mask);
1711 rdd = &dfly_pcpu[cpuid];
1713 if ((rdd->upri & ~PPQMASK) >= (lp->lwp_priority & ~PPQMASK))
1715 mask &= ~CPUMASK(cpuid);
1719 * Then cpus which might have a currently running lp
1721 cpuid = (dfly_scancpu & 0xFFFF) % ncpus;
1722 mask = dfly_curprocmask & dfly_rdyprocmask &
1723 lp->lwp_cpumask & smp_active_mask & usched_global_cpumask;
1726 tmpmask = ~(CPUMASK(cpuid) - 1);
1728 cpuid = BSFCPUMASK(mask & tmpmask);
1730 cpuid = BSFCPUMASK(mask);
1731 rdd = &dfly_pcpu[cpuid];
1733 if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK))
1735 mask &= ~CPUMASK(cpuid);
1739 * If we cannot find a suitable cpu we reload from dfly_scancpu
1740 * and round-robin. Other cpus will pickup as they release their
1741 * current lwps or become ready.
1743 * Avoid a degenerate system lockup case if usched_global_cpumask
1744 * is set to 0 or otherwise does not cover lwp_cpumask.
1746 * We only kick the target helper thread in this case, we do not
1747 * set the user resched flag because
1749 cpuid = (dfly_scancpu & 0xFFFF) % ncpus;
1750 if ((CPUMASK(cpuid) & usched_global_cpumask) == 0)
1752 rdd = &dfly_pcpu[cpuid];
1759 dfly_need_user_resched_remote(void *dummy)
1761 globaldata_t gd = mycpu;
1762 dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
1764 need_user_resched();
1766 /* Call wakeup_mycpu to avoid sending IPIs to other CPUs */
1767 wakeup_mycpu(&dd->helper_thread);
1773 * dfly_remrunqueue_locked() removes a given process from the run queue
1774 * that it is on, clearing the queue busy bit if it becomes empty.
1776 * Note that user process scheduler is different from the LWKT schedule.
1777 * The user process scheduler only manages user processes but it uses LWKT
1778 * underneath, and a user process operating in the kernel will often be
1779 * 'released' from our management.
1781 * uload is NOT adjusted here. It is only adjusted if the lwkt_thread goes
1782 * to sleep or the lwp is moved to a different runq.
1785 dfly_remrunqueue_locked(dfly_pcpu_t rdd, struct lwp *lp)
1791 KKASSERT(rdd->runqcount >= 0);
1793 pri = lp->lwp_rqindex;
1795 switch(lp->lwp_rqtype) {
1796 case RTP_PRIO_NORMAL:
1797 q = &rdd->queues[pri];
1798 which = &rdd->queuebits;
1800 case RTP_PRIO_REALTIME:
1802 q = &rdd->rtqueues[pri];
1803 which = &rdd->rtqueuebits;
1806 q = &rdd->idqueues[pri];
1807 which = &rdd->idqueuebits;
1810 panic("remrunqueue: invalid rtprio type");
1813 KKASSERT(lp->lwp_mpflags & LWP_MP_ONRUNQ);
1814 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
1815 TAILQ_REMOVE(q, lp, lwp_procq);
1817 if (TAILQ_EMPTY(q)) {
1818 KASSERT((*which & (1 << pri)) != 0,
1819 ("remrunqueue: remove from empty queue"));
1820 *which &= ~(1 << pri);
1825 * dfly_setrunqueue_locked()
1827 * Add a process whos rqtype and rqindex had previously been calculated
1828 * onto the appropriate run queue. Determine if the addition requires
1829 * a reschedule on a cpu and return the cpuid or -1.
1831 * NOTE: Lower priorities are better priorities.
1833 * NOTE ON ULOAD: This variable specifies the aggregate load on a cpu, the
1834 * sum of the rough lwp_priority for all running and runnable
1835 * processes. Lower priority processes (higher lwp_priority
1836 * values) actually DO count as more load, not less, because
1837 * these are the programs which require the most care with
1838 * regards to cpu selection.
1841 dfly_setrunqueue_locked(dfly_pcpu_t rdd, struct lwp *lp)
1847 KKASSERT(lp->lwp_qcpu == rdd->cpuid);
1849 if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) {
1850 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
1851 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].uload,
1852 (lp->lwp_priority & ~PPQMASK) & PRIMASK);
1853 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].ucount, 1);
1856 pri = lp->lwp_rqindex;
1858 switch(lp->lwp_rqtype) {
1859 case RTP_PRIO_NORMAL:
1860 q = &rdd->queues[pri];
1861 which = &rdd->queuebits;
1863 case RTP_PRIO_REALTIME:
1865 q = &rdd->rtqueues[pri];
1866 which = &rdd->rtqueuebits;
1869 q = &rdd->idqueues[pri];
1870 which = &rdd->idqueuebits;
1873 panic("remrunqueue: invalid rtprio type");
1878 * Add to the correct queue and set the appropriate bit. If no
1879 * lower priority (i.e. better) processes are in the queue then
1880 * we want a reschedule, calculate the best cpu for the job.
1882 * Always run reschedules on the LWPs original cpu.
1884 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
1885 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
1887 TAILQ_INSERT_TAIL(q, lp, lwp_procq);
1894 * For SMP systems a user scheduler helper thread is created for each
1895 * cpu and is used to allow one cpu to wakeup another for the purposes of
1896 * scheduling userland threads from setrunqueue().
1898 * UP systems do not need the helper since there is only one cpu.
1900 * We can't use the idle thread for this because we might block.
1901 * Additionally, doing things this way allows us to HLT idle cpus
1905 dfly_helper_thread(void *dummy)
1915 cpuid = gd->gd_cpuid; /* doesn't change */
1916 mask = gd->gd_cpumask; /* doesn't change */
1917 dd = &dfly_pcpu[cpuid];
1920 * Since we only want to be woken up only when no user processes
1921 * are scheduled on a cpu, run at an ultra low priority.
1923 lwkt_setpri_self(TDPRI_USER_SCHEDULER);
1925 tsleep(&dd->helper_thread, 0, "schslp", 0);
1929 * We use the LWKT deschedule-interlock trick to avoid racing
1930 * dfly_rdyprocmask. This means we cannot block through to the
1931 * manual lwkt_switch() call we make below.
1934 tsleep_interlock(&dd->helper_thread, 0);
1936 spin_lock(&dd->spin);
1938 atomic_set_cpumask(&dfly_rdyprocmask, mask);
1939 clear_user_resched(); /* This satisfied the reschedule request */
1940 dd->rrcount = 0; /* Reset the round-robin counter */
1942 if (dd->runqcount || dd->uschedcp != NULL) {
1944 * Threads are available. A thread may or may not be
1945 * currently scheduled. Get the best thread already queued
1948 nlp = dfly_chooseproc_locked(dd, dd, dd->uschedcp, 0);
1950 atomic_set_cpumask(&dfly_curprocmask, mask);
1951 dd->upri = nlp->lwp_priority;
1953 dd->rrcount = 0; /* reset round robin */
1954 spin_unlock(&dd->spin);
1955 lwkt_acquire(nlp->lwp_thread);
1956 lwkt_schedule(nlp->lwp_thread);
1959 * This situation should not occur because we had
1960 * at least one thread available.
1962 spin_unlock(&dd->spin);
1964 } else if (usched_dfly_features & 0x01) {
1966 * This cpu is devoid of runnable threads, steal a thread
1967 * from another cpu. Since we're stealing, might as well
1968 * load balance at the same time.
1970 * NOTE! This function only returns a non-NULL rdd when
1971 * another cpu's queue is obviously overloaded. We
1972 * do not want to perform the type of rebalancing
1973 * the schedclock does here because it would result
1974 * in insane process pulling when 'steady' state is
1975 * partially unbalanced (e.g. 6 runnables and only
1978 rdd = dfly_choose_worst_queue(dd);
1979 if (rdd && spin_trylock(&rdd->spin)) {
1980 nlp = dfly_chooseproc_locked(rdd, dd, NULL, 0);
1981 spin_unlock(&rdd->spin);
1986 atomic_set_cpumask(&dfly_curprocmask, mask);
1987 dd->upri = nlp->lwp_priority;
1989 dd->rrcount = 0; /* reset round robin */
1990 spin_unlock(&dd->spin);
1991 lwkt_acquire(nlp->lwp_thread);
1992 lwkt_schedule(nlp->lwp_thread);
1995 * Leave the thread on our run queue. Another
1996 * scheduler will try to pull it later.
1998 spin_unlock(&dd->spin);
2002 * devoid of runnable threads and not allowed to steal
2005 spin_unlock(&dd->spin);
2009 * We're descheduled unless someone scheduled us. Switch away.
2010 * Exiting the critical section will cause splz() to be called
2011 * for us if interrupts and such are pending.
2014 tsleep(&dd->helper_thread, PINTERLOCKED, "schslp", 0);
2020 sysctl_usched_dfly_stick_to_level(SYSCTL_HANDLER_ARGS)
2024 new_val = usched_dfly_stick_to_level;
2026 error = sysctl_handle_int(oidp, &new_val, 0, req);
2027 if (error != 0 || req->newptr == NULL)
2029 if (new_val > cpu_topology_levels_number - 1 || new_val < 0)
2031 usched_dfly_stick_to_level = new_val;
2037 * Setup our scheduler helpers. Note that curprocmask bit 0 has already
2038 * been cleared by rqinit() and we should not mess with it further.
2041 dfly_helper_thread_cpu_init(void)
2046 int smt_not_supported = 0;
2047 int cache_coherent_not_supported = 0;
2050 kprintf("Start scheduler helpers on cpus:\n");
2052 sysctl_ctx_init(&usched_dfly_sysctl_ctx);
2053 usched_dfly_sysctl_tree =
2054 SYSCTL_ADD_NODE(&usched_dfly_sysctl_ctx,
2055 SYSCTL_STATIC_CHILDREN(_kern), OID_AUTO,
2056 "usched_dfly", CTLFLAG_RD, 0, "");
2058 for (i = 0; i < ncpus; ++i) {
2059 dfly_pcpu_t dd = &dfly_pcpu[i];
2060 cpumask_t mask = CPUMASK(i);
2062 if ((mask & smp_active_mask) == 0)
2065 spin_init(&dd->spin);
2066 dd->cpunode = get_cpu_node_by_cpuid(i);
2068 dd->cpumask = CPUMASK(i);
2069 for (j = 0; j < NQS; j++) {
2070 TAILQ_INIT(&dd->queues[j]);
2071 TAILQ_INIT(&dd->rtqueues[j]);
2072 TAILQ_INIT(&dd->idqueues[j]);
2074 atomic_clear_cpumask(&dfly_curprocmask, 1);
2076 if (dd->cpunode == NULL) {
2077 smt_not_supported = 1;
2078 cache_coherent_not_supported = 1;
2080 kprintf ("\tcpu%d - WARNING: No CPU NODE "
2081 "found for cpu\n", i);
2083 switch (dd->cpunode->type) {
2086 kprintf ("\tcpu%d - HyperThreading "
2087 "available. Core siblings: ",
2091 smt_not_supported = 1;
2094 kprintf ("\tcpu%d - No HT available, "
2095 "multi-core/physical "
2096 "cpu. Physical siblings: ",
2100 smt_not_supported = 1;
2103 kprintf ("\tcpu%d - No HT available, "
2104 "single-core/physical cpu. "
2105 "Package Siblings: ",
2109 /* Let's go for safe defaults here */
2110 smt_not_supported = 1;
2111 cache_coherent_not_supported = 1;
2113 kprintf ("\tcpu%d - Unknown cpunode->"
2114 "type=%u. Siblings: ",
2116 (u_int)dd->cpunode->type);
2121 if (dd->cpunode->parent_node != NULL) {
2122 CPUSET_FOREACH(cpuid, dd->cpunode->parent_node->members)
2123 kprintf("cpu%d ", cpuid);
2126 kprintf(" no siblings\n");
2131 lwkt_create(dfly_helper_thread, NULL, NULL, &dd->helper_thread,
2132 0, i, "usched %d", i);
2135 * Allow user scheduling on the target cpu. cpu #0 has already
2136 * been enabled in rqinit().
2139 atomic_clear_cpumask(&dfly_curprocmask, mask);
2140 atomic_set_cpumask(&dfly_rdyprocmask, mask);
2141 dd->upri = PRIBASE_NULL;
2145 /* usched_dfly sysctl configurable parameters */
2147 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2148 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2149 OID_AUTO, "rrinterval", CTLFLAG_RW,
2150 &usched_dfly_rrinterval, 0, "");
2151 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2152 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2153 OID_AUTO, "decay", CTLFLAG_RW,
2154 &usched_dfly_decay, 0, "Extra decay when not running");
2155 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2156 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2157 OID_AUTO, "batch_time", CTLFLAG_RW,
2158 &usched_dfly_batch_time, 0, "Min batch counter value");
2160 /* Add enable/disable option for SMT scheduling if supported */
2161 if (smt_not_supported) {
2162 usched_dfly_smt = 0;
2163 SYSCTL_ADD_STRING(&usched_dfly_sysctl_ctx,
2164 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2165 OID_AUTO, "smt", CTLFLAG_RD,
2166 "NOT SUPPORTED", 0, "SMT NOT SUPPORTED");
2168 usched_dfly_smt = 1;
2169 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2170 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2171 OID_AUTO, "smt", CTLFLAG_RW,
2172 &usched_dfly_smt, 0, "Enable SMT scheduling");
2176 * Add enable/disable option for cache coherent scheduling
2179 if (cache_coherent_not_supported) {
2180 usched_dfly_cache_coherent = 0;
2181 SYSCTL_ADD_STRING(&usched_dfly_sysctl_ctx,
2182 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2183 OID_AUTO, "cache_coherent", CTLFLAG_RD,
2185 "Cache coherence NOT SUPPORTED");
2187 usched_dfly_cache_coherent = 1;
2188 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2189 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2190 OID_AUTO, "cache_coherent", CTLFLAG_RW,
2191 &usched_dfly_cache_coherent, 0,
2192 "Enable/Disable cache coherent scheduling");
2194 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2195 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2196 OID_AUTO, "weight1", CTLFLAG_RW,
2197 &usched_dfly_weight1, 10,
2198 "Weight selection for current cpu");
2200 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2201 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2202 OID_AUTO, "weight2", CTLFLAG_RW,
2203 &usched_dfly_weight2, 5,
2204 "Weight selection for wakefrom cpu");
2206 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2207 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2208 OID_AUTO, "weight3", CTLFLAG_RW,
2209 &usched_dfly_weight3, 50,
2210 "Weight selection for num threads on queue");
2212 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2213 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2214 OID_AUTO, "weight4", CTLFLAG_RW,
2215 &usched_dfly_weight4, 50,
2216 "Availability of other idle cpus");
2218 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2219 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2220 OID_AUTO, "features", CTLFLAG_RW,
2221 &usched_dfly_features, 15,
2222 "Allow pulls into empty queues");
2226 SYSCTL_ADD_PROC(&usched_dfly_sysctl_ctx,
2227 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2228 OID_AUTO, "stick_to_level",
2229 CTLTYPE_INT | CTLFLAG_RW,
2230 NULL, sizeof usched_dfly_stick_to_level,
2231 sysctl_usched_dfly_stick_to_level, "I",
2232 "Stick a process to this level. See sysctl"
2233 "paremter hw.cpu_topology.level_description");
2237 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND,
2238 dfly_helper_thread_cpu_init, NULL)
2240 #else /* No SMP options - just add the configurable parameters to sysctl */
2243 sched_sysctl_tree_init(void)
2245 sysctl_ctx_init(&usched_dfly_sysctl_ctx);
2246 usched_dfly_sysctl_tree =
2247 SYSCTL_ADD_NODE(&usched_dfly_sysctl_ctx,
2248 SYSCTL_STATIC_CHILDREN(_kern), OID_AUTO,
2249 "usched_dfly", CTLFLAG_RD, 0, "");
2251 /* usched_dfly sysctl configurable parameters */
2252 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2253 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2254 OID_AUTO, "rrinterval", CTLFLAG_RW,
2255 &usched_dfly_rrinterval, 0, "");
2256 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2257 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2258 OID_AUTO, "decay", CTLFLAG_RW,
2259 &usched_dfly_decay, 0, "Extra decay when not running");
2260 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2261 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2262 OID_AUTO, "batch_time", CTLFLAG_RW,
2263 &usched_dfly_batch_time, 0, "Min batch counter value");
2265 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND,
2266 sched_sysctl_tree_init, NULL)