96b5ccf8843b063ff430add195025a1f9e4787e5
[dragonfly.git] / sys / kern / usched_dfly.c
1 /*
2  * Copyright (c) 2012 The DragonFly Project.  All rights reserved.
3  * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org>.  All rights reserved.
4  *
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>
8  * and many others.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  *
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
19  *    distribution.
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.
23  *
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
35  * SUCH DAMAGE.
36  */
37 #include <sys/param.h>
38 #include <sys/systm.h>
39 #include <sys/kernel.h>
40 #include <sys/lock.h>
41 #include <sys/queue.h>
42 #include <sys/proc.h>
43 #include <sys/rtprio.h>
44 #include <sys/uio.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>
52
53 #include <sys/ktr.h>
54
55 #include <machine/cpu.h>
56 #include <machine/smp.h>
57
58 /*
59  * Priorities.  Note that with 32 run queues per scheduler each queue
60  * represents four priority levels.
61  */
62
63 int dfly_rebalanced;
64
65 #define MAXPRI                  128
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)
72
73 #define NQS     32                      /* 32 run queues. */
74 #define PPQ     (MAXPRI / NQS)          /* priorities per queue */
75 #define PPQMASK (PPQ - 1)
76
77 /*
78  * NICEPPQ      - number of nice units per priority queue
79  * ESTCPUPPQ    - number of estcpu units per priority queue
80  * ESTCPUMAX    - number of estcpu units
81  */
82 #define NICEPPQ         2
83 #define ESTCPUPPQ       512
84 #define ESTCPUMAX       (ESTCPUPPQ * NQS)
85 #define BATCHMAX        (ESTCPUFREQ * 30)
86 #define PRIO_RANGE      (PRIO_MAX - PRIO_MIN + 1)
87
88 #define ESTCPULIM(v)    min((v), ESTCPUMAX)
89
90 TAILQ_HEAD(rq, lwp);
91
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_estfast     lwp_usdata.dfly.estfast
97 #define lwp_uload       lwp_usdata.dfly.uload
98 #define lwp_rqtype      lwp_usdata.dfly.rqtype
99 #define lwp_qcpu        lwp_usdata.dfly.qcpu
100 #define lwp_rrcount     lwp_usdata.dfly.rrcount
101
102 struct usched_dfly_pcpu {
103         struct spinlock spin;
104         struct thread   helper_thread;
105         short           unusde01;
106         short           upri;
107         int             uload;
108         int             ucount;
109         struct lwp      *uschedcp;
110         struct rq       queues[NQS];
111         struct rq       rtqueues[NQS];
112         struct rq       idqueues[NQS];
113         u_int32_t       queuebits;
114         u_int32_t       rtqueuebits;
115         u_int32_t       idqueuebits;
116         int             runqcount;
117         int             cpuid;
118         cpumask_t       cpumask;
119 #ifdef SMP
120         cpu_node_t      *cpunode;
121 #endif
122 };
123
124 typedef struct usched_dfly_pcpu *dfly_pcpu_t;
125
126 static void dfly_acquire_curproc(struct lwp *lp);
127 static void dfly_release_curproc(struct lwp *lp);
128 static void dfly_select_curproc(globaldata_t gd);
129 static void dfly_setrunqueue(struct lwp *lp);
130 static void dfly_setrunqueue_dd(dfly_pcpu_t rdd, struct lwp *lp);
131 static void dfly_schedulerclock(struct lwp *lp, sysclock_t period,
132                                 sysclock_t cpstamp);
133 static void dfly_recalculate_estcpu(struct lwp *lp);
134 static void dfly_resetpriority(struct lwp *lp);
135 static void dfly_forking(struct lwp *plp, struct lwp *lp);
136 static void dfly_exiting(struct lwp *lp, struct proc *);
137 static void dfly_uload_update(struct lwp *lp);
138 static void dfly_yield(struct lwp *lp);
139 #ifdef SMP
140 static void dfly_changeqcpu_locked(struct lwp *lp,
141                                 dfly_pcpu_t dd, dfly_pcpu_t rdd);
142 static dfly_pcpu_t dfly_choose_best_queue(struct lwp *lp);
143 static dfly_pcpu_t dfly_choose_worst_queue(dfly_pcpu_t dd);
144 static dfly_pcpu_t dfly_choose_queue_simple(dfly_pcpu_t dd, struct lwp *lp);
145 #endif
146
147 #ifdef SMP
148 static void dfly_need_user_resched_remote(void *dummy);
149 #endif
150 static struct lwp *dfly_chooseproc_locked(dfly_pcpu_t rdd, dfly_pcpu_t dd,
151                                           struct lwp *chklp, int worst);
152 static void dfly_remrunqueue_locked(dfly_pcpu_t dd, struct lwp *lp);
153 static void dfly_setrunqueue_locked(dfly_pcpu_t dd, struct lwp *lp);
154
155 struct usched usched_dfly = {
156         { NULL },
157         "dfly", "Original DragonFly Scheduler",
158         NULL,                   /* default registration */
159         NULL,                   /* default deregistration */
160         dfly_acquire_curproc,
161         dfly_release_curproc,
162         dfly_setrunqueue,
163         dfly_schedulerclock,
164         dfly_recalculate_estcpu,
165         dfly_resetpriority,
166         dfly_forking,
167         dfly_exiting,
168         dfly_uload_update,
169         NULL,                   /* setcpumask not supported */
170         dfly_yield
171 };
172
173 /*
174  * We have NQS (32) run queues per scheduling class.  For the normal
175  * class, there are 128 priorities scaled onto these 32 queues.  New
176  * processes are added to the last entry in each queue, and processes
177  * are selected for running by taking them from the head and maintaining
178  * a simple FIFO arrangement.  Realtime and Idle priority processes have
179  * and explicit 0-31 priority which maps directly onto their class queue
180  * index.  When a queue has something in it, the corresponding bit is
181  * set in the queuebits variable, allowing a single read to determine
182  * the state of all 32 queues and then a ffs() to find the first busy
183  * queue.
184  */
185 static cpumask_t dfly_curprocmask = -1; /* currently running a user process */
186 static cpumask_t dfly_rdyprocmask;      /* ready to accept a user process */
187 #ifdef SMP
188 static volatile int dfly_scancpu;
189 #endif
190 static volatile int dfly_ucount;        /* total running on whole system */
191 static struct usched_dfly_pcpu dfly_pcpu[MAXCPU];
192 static struct sysctl_ctx_list usched_dfly_sysctl_ctx;
193 static struct sysctl_oid *usched_dfly_sysctl_tree;
194
195 /* Debug info exposed through debug.* sysctl */
196
197 static int usched_dfly_debug = -1;
198 SYSCTL_INT(_debug, OID_AUTO, dfly_scdebug, CTLFLAG_RW,
199            &usched_dfly_debug, 0,
200            "Print debug information for this pid");
201
202 static int usched_dfly_pid_debug = -1;
203 SYSCTL_INT(_debug, OID_AUTO, dfly_pid_debug, CTLFLAG_RW,
204            &usched_dfly_pid_debug, 0,
205            "Print KTR debug information for this pid");
206
207 static int usched_dfly_chooser = 0;
208 SYSCTL_INT(_debug, OID_AUTO, dfly_chooser, CTLFLAG_RW,
209            &usched_dfly_chooser, 0,
210            "Print KTR debug information for this pid");
211
212 /*
213  * Tunning usched_dfly - configurable through kern.usched_dfly.
214  *
215  * weight1 - Tries to keep threads on their current cpu.  If you
216  *           make this value too large the scheduler will not be
217  *           able to load-balance large loads.
218  *
219  * weight2 - If non-zero, detects thread pairs undergoing synchronous
220  *           communications and tries to move them closer together.
221  *           Behavior is adjusted by bit 4 of features (0x10).
222  *
223  *           WARNING!  Weight2 is a ridiculously sensitive parameter,
224  *           a small value is recommended.
225  *
226  * weight3 - Weighting based on the number of recently runnable threads
227  *           on the userland scheduling queue (ignoring their loads).
228  *           A nominal value here prevents high-priority (low-load)
229  *           threads from accumulating on one cpu core when other
230  *           cores are available.
231  *
232  *           This value should be left fairly small relative to weight1
233  *           and weight4.
234  *
235  * weight4 - Weighting based on other cpu queues being available
236  *           or running processes with higher lwp_priority's.
237  *
238  *           This allows a thread to migrate to another nearby cpu if it
239  *           is unable to run on the current cpu based on the other cpu
240  *           being idle or running a lower priority (higher lwp_priority)
241  *           thread.  This value should be large enough to override weight1
242  *
243  * features - These flags can be set or cleared to enable or disable various
244  *            features.
245  *
246  *            0x01      Enable idle-cpu pulling                 (default)
247  *            0x02      Enable proactive pushing                (default)
248  *            0x04      Enable rebalancing rover                (default)
249  *            0x08      Enable more proactive pushing           (default)
250  *            0x10      (flip weight2 limit on same cpu)        (default)
251  *            0x20      choose best cpu for forked process
252  *            0x40      choose current cpu for forked process
253  *            0x80      choose random cpu for forked process    (default)
254  */
255 #ifdef SMP
256 static int usched_dfly_smt = 0;
257 static int usched_dfly_cache_coherent = 0;
258 static int usched_dfly_weight1 = 200;   /* keep thread on current cpu */
259 static int usched_dfly_weight2 = 180;   /* synchronous peer's current cpu */
260 static int usched_dfly_weight3 = 40;    /* number of threads on queue */
261 static int usched_dfly_weight4 = 160;   /* availability of idle cores */
262 static int usched_dfly_features = 0x8F; /* allow pulls */
263 #endif
264 static int usched_dfly_fast_resched = 0;/* delta priority / resched */
265 static int usched_dfly_swmask = ~PPQMASK; /* allow pulls */
266 static int usched_dfly_rrinterval = (ESTCPUFREQ + 9) / 10;
267 static int usched_dfly_decay = 8;
268
269 /* KTR debug printings */
270
271 KTR_INFO_MASTER(usched);
272
273 #if !defined(KTR_USCHED_DFLY)
274 #define KTR_USCHED_DFLY KTR_ALL
275 #endif
276
277 KTR_INFO(KTR_USCHED_DFLY, usched, chooseproc, 0,
278     "USCHED_DFLY(chooseproc: pid %d, old_cpuid %d, curr_cpuid %d)",
279     pid_t pid, int old_cpuid, int curr);
280
281 /*
282  * This function is called when the kernel intends to return to userland.
283  * It is responsible for making the thread the current designated userland
284  * thread for this cpu, blocking if necessary.
285  *
286  * The kernel will not depress our LWKT priority until after we return,
287  * in case we have to shove over to another cpu.
288  *
289  * We must determine our thread's disposition before we switch away.  This
290  * is very sensitive code.
291  *
292  * WARNING! THIS FUNCTION IS ALLOWED TO CAUSE THE CURRENT THREAD TO MIGRATE
293  * TO ANOTHER CPU!  Because most of the kernel assumes that no migration will
294  * occur, this function is called only under very controlled circumstances.
295  */
296 static void
297 dfly_acquire_curproc(struct lwp *lp)
298 {
299         globaldata_t gd;
300         dfly_pcpu_t dd;
301 #ifdef SMP
302         dfly_pcpu_t rdd;
303 #endif
304         thread_t td;
305         int force_resched;
306
307         /*
308          * Make sure we aren't sitting on a tsleep queue.
309          */
310         td = lp->lwp_thread;
311         crit_enter_quick(td);
312         if (td->td_flags & TDF_TSLEEPQ)
313                 tsleep_remove(td);
314         dfly_recalculate_estcpu(lp);
315
316         gd = mycpu;
317         dd = &dfly_pcpu[gd->gd_cpuid];
318
319         /*
320          * Process any pending interrupts/ipi's, then handle reschedule
321          * requests.  dfly_release_curproc() will try to assign a new
322          * uschedcp that isn't us and otherwise NULL it out.
323          */
324         force_resched = 0;
325         if ((td->td_mpflags & TDF_MP_BATCH_DEMARC) &&
326             lp->lwp_rrcount >= usched_dfly_rrinterval / 2) {
327                 force_resched = 1;
328         }
329
330         if (user_resched_wanted()) {
331                 if (dd->uschedcp == lp)
332                         force_resched = 1;
333                 clear_user_resched();
334                 dfly_release_curproc(lp);
335         }
336
337         /*
338          * Loop until we are the current user thread.
339          *
340          * NOTE: dd spinlock not held at top of loop.
341          */
342         if (dd->uschedcp == lp)
343                 lwkt_yield_quick();
344
345         while (dd->uschedcp != lp) {
346                 lwkt_yield_quick();
347
348                 spin_lock(&dd->spin);
349
350                 /*
351                  * We are not or are no longer the current lwp and a forced
352                  * reschedule was requested.  Figure out the best cpu to
353                  * run on (our current cpu will be given significant weight).
354                  *
355                  * (if a reschedule was not requested we want to move this
356                  *  step after the uschedcp tests).
357                  */
358 #ifdef SMP
359                 if (force_resched &&
360                     (usched_dfly_features & 0x08) &&
361                     (rdd = dfly_choose_best_queue(lp)) != dd) {
362                         dfly_changeqcpu_locked(lp, dd, rdd);
363                         spin_unlock(&dd->spin);
364                         lwkt_deschedule(lp->lwp_thread);
365                         dfly_setrunqueue_dd(rdd, lp);
366                         lwkt_switch();
367                         gd = mycpu;
368                         dd = &dfly_pcpu[gd->gd_cpuid];
369                         continue;
370                 }
371 #endif
372
373                 /*
374                  * Either no reschedule was requested or the best queue was
375                  * dd, and no current process has been selected.  We can
376                  * trivially become the current lwp on the current cpu.
377                  */
378                 if (dd->uschedcp == NULL) {
379                         atomic_set_cpumask(&dfly_curprocmask, gd->gd_cpumask);
380                         dd->uschedcp = lp;
381                         dd->upri = lp->lwp_priority;
382                         KKASSERT(lp->lwp_qcpu == dd->cpuid);
383                         spin_unlock(&dd->spin);
384                         break;
385                 }
386
387                 /*
388                  * Can we steal the current designated user thread?
389                  *
390                  * If we do the other thread will stall when it tries to
391                  * return to userland, possibly rescheduling elsewhere.
392                  *
393                  * It is important to do a masked test to avoid the edge
394                  * case where two near-equal-priority threads are constantly
395                  * interrupting each other.
396                  *
397                  * In the exact match case another thread has already gained
398                  * uschedcp and lowered its priority, if we steal it the
399                  * other thread will stay stuck on the LWKT runq and not
400                  * push to another cpu.  So don't steal on equal-priority even
401                  * though it might appear to be more beneficial due to not
402                  * having to switch back to the other thread's context.
403                  *
404                  * usched_dfly_fast_resched requires that two threads be
405                  * significantly far apart in priority in order to interrupt.
406                  *
407                  * If better but not sufficiently far apart, the current
408                  * uschedcp will be interrupted at the next scheduler clock.
409                  */
410                 if (dd->uschedcp &&
411                    (dd->upri & ~PPQMASK) >
412                    (lp->lwp_priority & ~PPQMASK) + usched_dfly_fast_resched) {
413                         dd->uschedcp = lp;
414                         dd->upri = lp->lwp_priority;
415                         KKASSERT(lp->lwp_qcpu == dd->cpuid);
416                         spin_unlock(&dd->spin);
417                         break;
418                 }
419 #ifdef SMP
420                 /*
421                  * We are not the current lwp, figure out the best cpu
422                  * to run on (our current cpu will be given significant
423                  * weight).  Loop on cpu change.
424                  */
425                 if ((usched_dfly_features & 0x02) &&
426                     force_resched == 0 &&
427                     (rdd = dfly_choose_best_queue(lp)) != dd) {
428                         dfly_changeqcpu_locked(lp, dd, rdd);
429                         spin_unlock(&dd->spin);
430                         lwkt_deschedule(lp->lwp_thread);
431                         dfly_setrunqueue_dd(rdd, lp);
432                         lwkt_switch();
433                         gd = mycpu;
434                         dd = &dfly_pcpu[gd->gd_cpuid];
435                         continue;
436                 }
437 #endif
438
439                 /*
440                  * We cannot become the current lwp, place the lp on the
441                  * run-queue of this or another cpu and deschedule ourselves.
442                  *
443                  * When we are reactivated we will have another chance.
444                  *
445                  * Reload after a switch or setrunqueue/switch possibly
446                  * moved us to another cpu.
447                  */
448                 spin_unlock(&dd->spin);
449                 lwkt_deschedule(lp->lwp_thread);
450                 dfly_setrunqueue_dd(dd, lp);
451                 lwkt_switch();
452                 gd = mycpu;
453                 dd = &dfly_pcpu[gd->gd_cpuid];
454         }
455
456         /*
457          * Make sure upri is synchronized, then yield to LWKT threads as
458          * needed before returning.  This could result in another reschedule.
459          * XXX
460          */
461         crit_exit_quick(td);
462
463         KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
464 }
465
466 /*
467  * DFLY_RELEASE_CURPROC
468  *
469  * This routine detaches the current thread from the userland scheduler,
470  * usually because the thread needs to run or block in the kernel (at
471  * kernel priority) for a while.
472  *
473  * This routine is also responsible for selecting a new thread to
474  * make the current thread.
475  *
476  * NOTE: This implementation differs from the dummy example in that
477  * dfly_select_curproc() is able to select the current process, whereas
478  * dummy_select_curproc() is not able to select the current process.
479  * This means we have to NULL out uschedcp.
480  *
481  * Additionally, note that we may already be on a run queue if releasing
482  * via the lwkt_switch() in dfly_setrunqueue().
483  */
484 static void
485 dfly_release_curproc(struct lwp *lp)
486 {
487         globaldata_t gd = mycpu;
488         dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
489
490         /*
491          * Make sure td_wakefromcpu is defaulted.  This will be overwritten
492          * by wakeup().
493          */
494         if (dd->uschedcp == lp) {
495                 KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
496                 spin_lock(&dd->spin);
497                 if (dd->uschedcp == lp) {
498                         dd->uschedcp = NULL;    /* don't let lp be selected */
499                         dd->upri = PRIBASE_NULL;
500                         atomic_clear_cpumask(&dfly_curprocmask, gd->gd_cpumask);
501                         spin_unlock(&dd->spin);
502                         dfly_select_curproc(gd);
503                 } else {
504                         spin_unlock(&dd->spin);
505                 }
506         }
507 }
508
509 /*
510  * DFLY_SELECT_CURPROC
511  *
512  * Select a new current process for this cpu and clear any pending user
513  * reschedule request.  The cpu currently has no current process.
514  *
515  * This routine is also responsible for equal-priority round-robining,
516  * typically triggered from dfly_schedulerclock().  In our dummy example
517  * all the 'user' threads are LWKT scheduled all at once and we just
518  * call lwkt_switch().
519  *
520  * The calling process is not on the queue and cannot be selected.
521  */
522 static
523 void
524 dfly_select_curproc(globaldata_t gd)
525 {
526         dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
527         struct lwp *nlp;
528         int cpuid = gd->gd_cpuid;
529
530         crit_enter_gd(gd);
531
532         spin_lock(&dd->spin);
533         nlp = dfly_chooseproc_locked(dd, dd, dd->uschedcp, 0);
534
535         if (nlp) {
536                 atomic_set_cpumask(&dfly_curprocmask, CPUMASK(cpuid));
537                 dd->upri = nlp->lwp_priority;
538                 dd->uschedcp = nlp;
539 #if 0
540                 dd->rrcount = 0;                /* reset round robin */
541 #endif
542                 spin_unlock(&dd->spin);
543 #ifdef SMP
544                 lwkt_acquire(nlp->lwp_thread);
545 #endif
546                 lwkt_schedule(nlp->lwp_thread);
547         } else {
548                 spin_unlock(&dd->spin);
549         }
550         crit_exit_gd(gd);
551 }
552
553 /*
554  * Place the specified lwp on the user scheduler's run queue.  This routine
555  * must be called with the thread descheduled.  The lwp must be runnable.
556  * It must not be possible for anyone else to explicitly schedule this thread.
557  *
558  * The thread may be the current thread as a special case.
559  */
560 static void
561 dfly_setrunqueue(struct lwp *lp)
562 {
563         dfly_pcpu_t dd;
564         dfly_pcpu_t rdd;
565
566         /*
567          * First validate the process LWKT state.
568          */
569         KASSERT(lp->lwp_stat == LSRUN, ("setrunqueue: lwp not LSRUN"));
570         KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0,
571             ("lwp %d/%d already on runq! flag %08x/%08x", lp->lwp_proc->p_pid,
572              lp->lwp_tid, lp->lwp_proc->p_flags, lp->lwp_flags));
573         KKASSERT((lp->lwp_thread->td_flags & TDF_RUNQ) == 0);
574
575         /*
576          * NOTE: dd/rdd do not necessarily represent the current cpu.
577          *       Instead they may represent the cpu the thread was last
578          *       scheduled on or inherited by its parent.
579          */
580         dd = &dfly_pcpu[lp->lwp_qcpu];
581         rdd = dd;
582
583         /*
584          * This process is not supposed to be scheduled anywhere or assigned
585          * as the current process anywhere.  Assert the condition.
586          */
587         KKASSERT(rdd->uschedcp != lp);
588
589 #ifndef SMP
590         /*
591          * If we are not SMP we do not have a scheduler helper to kick
592          * and must directly activate the process if none are scheduled.
593          *
594          * This is really only an issue when bootstrapping init since
595          * the caller in all other cases will be a user process, and
596          * even if released (rdd->uschedcp == NULL), that process will
597          * kickstart the scheduler when it returns to user mode from
598          * the kernel.
599          *
600          * NOTE: On SMP we can't just set some other cpu's uschedcp.
601          */
602         if (rdd->uschedcp == NULL) {
603                 spin_lock(&rdd->spin);
604                 if (rdd->uschedcp == NULL) {
605                         atomic_set_cpumask(&dfly_curprocmask, 1);
606                         rdd->uschedcp = lp;
607                         rdd->upri = lp->lwp_priority;
608                         spin_unlock(&rdd->spin);
609                         lwkt_schedule(lp->lwp_thread);
610                         return;
611                 }
612                 spin_unlock(&rdd->spin);
613         }
614 #endif
615
616 #ifdef SMP
617         /*
618          * Ok, we have to setrunqueue some target cpu and request a reschedule
619          * if necessary.
620          *
621          * We have to choose the best target cpu.  It might not be the current
622          * target even if the current cpu has no running user thread (for
623          * example, because the current cpu might be a hyperthread and its
624          * sibling has a thread assigned).
625          *
626          * If we just forked it is most optimal to run the child on the same
627          * cpu just in case the parent decides to wait for it (thus getting
628          * off that cpu).  As long as there is nothing else runnable on the
629          * cpu, that is.  If we did this unconditionally a parent forking
630          * multiple children before waiting (e.g. make -j N) leaves other
631          * cpus idle that could be working.
632          */
633         if (lp->lwp_forked) {
634                 lp->lwp_forked = 0;
635                 if (usched_dfly_features & 0x20)
636                         rdd = dfly_choose_best_queue(lp);
637                 else if (usched_dfly_features & 0x40)
638                         rdd = &dfly_pcpu[lp->lwp_qcpu];
639                 else if (usched_dfly_features & 0x80)
640                         rdd = dfly_choose_queue_simple(rdd, lp);
641                 else if (dfly_pcpu[lp->lwp_qcpu].runqcount)
642                         rdd = dfly_choose_best_queue(lp);
643                 else
644                         rdd = &dfly_pcpu[lp->lwp_qcpu];
645         } else {
646                 rdd = dfly_choose_best_queue(lp);
647                 /* rdd = &dfly_pcpu[lp->lwp_qcpu]; */
648         }
649         if (lp->lwp_qcpu != rdd->cpuid) {
650                 spin_lock(&dd->spin);
651                 dfly_changeqcpu_locked(lp, dd, rdd);
652                 spin_unlock(&dd->spin);
653         }
654 #endif
655         dfly_setrunqueue_dd(rdd, lp);
656 }
657
658 #ifdef SMP
659
660 /*
661  * Change qcpu to rdd->cpuid.  The dd the lp is CURRENTLY on must be
662  * spin-locked on-call.  rdd does not have to be.
663  */
664 static void
665 dfly_changeqcpu_locked(struct lwp *lp, dfly_pcpu_t dd, dfly_pcpu_t rdd)
666 {
667         if (lp->lwp_qcpu != rdd->cpuid) {
668                 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
669                         atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
670                         atomic_add_int(&dd->uload, -lp->lwp_uload);
671                         atomic_add_int(&dd->ucount, -1);
672                         atomic_add_int(&dfly_ucount, -1);
673                 }
674                 lp->lwp_qcpu = rdd->cpuid;
675         }
676 }
677
678 #endif
679
680 /*
681  * Place lp on rdd's runqueue.  Nothing is locked on call.  This function
682  * also performs all necessary ancillary notification actions.
683  */
684 static void
685 dfly_setrunqueue_dd(dfly_pcpu_t rdd, struct lwp *lp)
686 {
687 #ifdef SMP
688         globaldata_t rgd;
689
690         /*
691          * We might be moving the lp to another cpu's run queue, and once
692          * on the runqueue (even if it is our cpu's), another cpu can rip
693          * it away from us.
694          *
695          * TDF_MIGRATING might already be set if this is part of a
696          * remrunqueue+setrunqueue sequence.
697          */
698         if ((lp->lwp_thread->td_flags & TDF_MIGRATING) == 0)
699                 lwkt_giveaway(lp->lwp_thread);
700
701         rgd = globaldata_find(rdd->cpuid);
702
703         /*
704          * We lose control of the lp the moment we release the spinlock
705          * after having placed it on the queue.  i.e. another cpu could pick
706          * it up, or it could exit, or its priority could be further
707          * adjusted, or something like that.
708          *
709          * WARNING! rdd can point to a foreign cpu!
710          */
711         spin_lock(&rdd->spin);
712         dfly_setrunqueue_locked(rdd, lp);
713
714         /*
715          * Potentially interrupt the currently-running thread
716          */
717         if ((rdd->upri & ~PPQMASK) <= (lp->lwp_priority & ~PPQMASK)) {
718                 /*
719                  * Currently running thread is better or same, do not
720                  * interrupt.
721                  */
722                 spin_unlock(&rdd->spin);
723         } else if ((rdd->upri & ~PPQMASK) <= (lp->lwp_priority & ~PPQMASK) +
724                    usched_dfly_fast_resched) {
725                 /*
726                  * Currently running thread is not better, but not so bad
727                  * that we need to interrupt it.  Let it run for one more
728                  * scheduler tick.
729                  */
730                 if (rdd->uschedcp &&
731                     rdd->uschedcp->lwp_rrcount < usched_dfly_rrinterval) {
732                         rdd->uschedcp->lwp_rrcount = usched_dfly_rrinterval - 1;
733                 }
734                 spin_unlock(&rdd->spin);
735         } else if (rgd == mycpu) {
736                 /*
737                  * We should interrupt the currently running thread, which
738                  * is on the current cpu.
739                  */
740                 spin_unlock(&rdd->spin);
741                 if (rdd->uschedcp == NULL) {
742                         wakeup_mycpu(&rdd->helper_thread); /* XXX */
743                         need_user_resched();
744                 } else {
745                         need_user_resched();
746                 }
747         } else {
748                 /*
749                  * We should interrupt the currently running thread, which
750                  * is on a different cpu.
751                  */
752                 spin_unlock(&rdd->spin);
753                 lwkt_send_ipiq(rgd, dfly_need_user_resched_remote, NULL);
754         }
755 #else
756         /*
757          * Request a reschedule if appropriate.
758          */
759         spin_lock(&rdd->spin);
760         dfly_setrunqueue_locked(rdd, lp);
761         spin_unlock(&rdd->spin);
762         if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK)) {
763                 need_user_resched();
764         }
765 #endif
766 }
767
768 /*
769  * This routine is called from a systimer IPI.  It MUST be MP-safe and
770  * the BGL IS NOT HELD ON ENTRY.  This routine is called at ESTCPUFREQ on
771  * each cpu.
772  */
773 static
774 void
775 dfly_schedulerclock(struct lwp *lp, sysclock_t period, sysclock_t cpstamp)
776 {
777         globaldata_t gd = mycpu;
778 #ifdef SMP
779         dfly_pcpu_t dd = &dfly_pcpu[gd->gd_cpuid];
780 #endif
781
782         /*
783          * Spinlocks also hold a critical section so there should not be
784          * any active.
785          */
786         KKASSERT(gd->gd_spinlocks == 0);
787
788         if (lp == NULL)
789                 return;
790
791         /*
792          * Do we need to round-robin?  We round-robin 10 times a second.
793          * This should only occur for cpu-bound batch processes.
794          */
795         if (++lp->lwp_rrcount >= usched_dfly_rrinterval) {
796                 lp->lwp_thread->td_wakefromcpu = -1;
797                 need_user_resched();
798         }
799
800         /*
801          * Adjust estcpu upward using a real time equivalent calculation,
802          * and recalculate lp's priority.
803          */
804         lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUMAX / ESTCPUFREQ + 1);
805         dfly_resetpriority(lp);
806
807         /*
808          * Rebalance two cpus every 8 ticks, pulling the worst thread
809          * from the worst cpu's queue into a rotating cpu number.
810          *
811          * This mechanic is needed because the push algorithms can
812          * steady-state in an non-optimal configuration.  We need to mix it
813          * up a little, even if it means breaking up a paired thread, so
814          * the push algorithms can rebalance the degenerate conditions.
815          * This portion of the algorithm exists to ensure stability at the
816          * selected weightings.
817          *
818          * Because we might be breaking up optimal conditions we do not want
819          * to execute this too quickly, hence we only rebalance approximately
820          * ~7-8 times per second.  The push's, on the otherhand, are capable
821          * moving threads to other cpus at a much higher rate.
822          *
823          * We choose the most heavily loaded thread from the worst queue
824          * in order to ensure that multiple heavy-weight threads on the same
825          * queue get broken up, and also because these threads are the most
826          * likely to be able to remain in place.  Hopefully then any pairings,
827          * if applicable, migrate to where these threads are.
828          */
829 #ifdef SMP
830         if ((usched_dfly_features & 0x04) &&
831             ((u_int)sched_ticks & 7) == 0 &&
832             (u_int)sched_ticks / 8 % ncpus == gd->gd_cpuid) {
833                 /*
834                  * Our cpu is up.
835                  */
836                 struct lwp *nlp;
837                 dfly_pcpu_t rdd;
838
839                 rdd = dfly_choose_worst_queue(dd);
840                 if (rdd) {
841                         spin_lock(&dd->spin);
842                         if (spin_trylock(&rdd->spin)) {
843                                 nlp = dfly_chooseproc_locked(rdd, dd, NULL, 1);
844                                 spin_unlock(&rdd->spin);
845                                 if (nlp == NULL)
846                                         spin_unlock(&dd->spin);
847                         } else {
848                                 spin_unlock(&dd->spin);
849                                 nlp = NULL;
850                         }
851                 } else {
852                         nlp = NULL;
853                 }
854                 /* dd->spin held if nlp != NULL */
855
856                 /*
857                  * Either schedule it or add it to our queue.
858                  */
859                 if (nlp &&
860                     (nlp->lwp_priority & ~PPQMASK) < (dd->upri & ~PPQMASK)) {
861                         atomic_set_cpumask(&dfly_curprocmask, dd->cpumask);
862                         dd->upri = nlp->lwp_priority;
863                         dd->uschedcp = nlp;
864 #if 0
865                         dd->rrcount = 0;        /* reset round robin */
866 #endif
867                         spin_unlock(&dd->spin);
868                         lwkt_acquire(nlp->lwp_thread);
869                         lwkt_schedule(nlp->lwp_thread);
870                 } else if (nlp) {
871                         dfly_setrunqueue_locked(dd, nlp);
872                         spin_unlock(&dd->spin);
873                 }
874         }
875 #endif
876 }
877
878 /*
879  * Called from acquire and from kern_synch's one-second timer (one of the
880  * callout helper threads) with a critical section held.
881  *
882  * Adjust p_estcpu based on our single-cpu load, p_nice, and compensate for
883  * overall system load.
884  *
885  * Note that no recalculation occurs for a process which sleeps and wakes
886  * up in the same tick.  That is, a system doing thousands of context
887  * switches per second will still only do serious estcpu calculations
888  * ESTCPUFREQ times per second.
889  */
890 static
891 void
892 dfly_recalculate_estcpu(struct lwp *lp)
893 {
894         globaldata_t gd = mycpu;
895         sysclock_t cpbase;
896         sysclock_t ttlticks;
897         int estcpu;
898         int decay_factor;
899         int ucount;
900
901         /*
902          * We have to subtract periodic to get the last schedclock
903          * timeout time, otherwise we would get the upcoming timeout.
904          * Keep in mind that a process can migrate between cpus and
905          * while the scheduler clock should be very close, boundary
906          * conditions could lead to a small negative delta.
907          */
908         cpbase = gd->gd_schedclock.time - gd->gd_schedclock.periodic;
909
910         if (lp->lwp_slptime > 1) {
911                 /*
912                  * Too much time has passed, do a coarse correction.
913                  */
914                 lp->lwp_estcpu = lp->lwp_estcpu >> 1;
915                 dfly_resetpriority(lp);
916                 lp->lwp_cpbase = cpbase;
917                 lp->lwp_cpticks = 0;
918                 lp->lwp_estfast = 0;
919         } else if (lp->lwp_cpbase != cpbase) {
920                 /*
921                  * Adjust estcpu if we are in a different tick.  Don't waste
922                  * time if we are in the same tick.
923                  *
924                  * First calculate the number of ticks in the measurement
925                  * interval.  The ttlticks calculation can wind up 0 due to
926                  * a bug in the handling of lwp_slptime  (as yet not found),
927                  * so make sure we do not get a divide by 0 panic.
928                  */
929                 ttlticks = (cpbase - lp->lwp_cpbase) /
930                            gd->gd_schedclock.periodic;
931                 if (ttlticks < 0) {
932                         ttlticks = 0;
933                         lp->lwp_cpbase = cpbase;
934                 }
935                 if (ttlticks == 0)
936                         return;
937                 updatepcpu(lp, lp->lwp_cpticks, ttlticks);
938
939                 /*
940                  * Calculate the percentage of one cpu being used then
941                  * compensate for any system load in excess of ncpus.
942                  *
943                  * For example, if we have 8 cores and 16 running cpu-bound
944                  * processes then all things being equal each process will
945                  * get 50% of one cpu.  We need to pump this value back
946                  * up to 100% so the estcpu calculation properly adjusts
947                  * the process's dynamic priority.
948                  *
949                  * estcpu is scaled by ESTCPUMAX, pctcpu is scaled by FSCALE.
950                  */
951                 estcpu = (lp->lwp_pctcpu * ESTCPUMAX) >> FSHIFT;
952                 ucount = dfly_ucount;
953                 if (ucount > ncpus) {
954                         estcpu += estcpu * (ucount - ncpus) / ncpus;
955                 }
956
957                 if (usched_dfly_debug == lp->lwp_proc->p_pid) {
958                         kprintf("pid %d lwp %p estcpu %3d %3d cp %d/%d",
959                                 lp->lwp_proc->p_pid, lp,
960                                 estcpu, lp->lwp_estcpu,
961                                 lp->lwp_cpticks, ttlticks);
962                 }
963
964                 /*
965                  * Adjust lp->lwp_esetcpu.  The decay factor determines how
966                  * quickly lwp_estcpu collapses to its realtime calculation.
967                  * A slower collapse gives us a more accurate number over
968                  * the long term but can create problems with bursty threads
969                  * or threads which become cpu hogs.
970                  *
971                  * To solve this problem, newly started lwps and lwps which
972                  * are restarting after having been asleep for a while are
973                  * given a much, much faster decay in order to quickly
974                  * detect whether they become cpu-bound.
975                  *
976                  * NOTE: p_nice is accounted for in dfly_resetpriority(),
977                  *       and not here, but we must still ensure that a
978                  *       cpu-bound nice -20 process does not completely
979                  *       override a cpu-bound nice +20 process.
980                  *
981                  * NOTE: We must use ESTCPULIM() here to deal with any
982                  *       overshoot.
983                  */
984                 decay_factor = usched_dfly_decay;
985                 if (decay_factor < 1)
986                         decay_factor = 1;
987                 if (decay_factor > 1024)
988                         decay_factor = 1024;
989
990                 if (lp->lwp_estfast < usched_dfly_decay) {
991                         ++lp->lwp_estfast;
992                         lp->lwp_estcpu = ESTCPULIM(
993                                 (lp->lwp_estcpu * lp->lwp_estfast + estcpu) /
994                                 (lp->lwp_estfast + 1));
995                 } else {
996                         lp->lwp_estcpu = ESTCPULIM(
997                                 (lp->lwp_estcpu * decay_factor + estcpu) /
998                                 (decay_factor + 1));
999                 }
1000
1001                 if (usched_dfly_debug == lp->lwp_proc->p_pid)
1002                         kprintf(" finalestcpu %d\n", lp->lwp_estcpu);
1003                 dfly_resetpriority(lp);
1004                 lp->lwp_cpbase += ttlticks * gd->gd_schedclock.periodic;
1005                 lp->lwp_cpticks = 0;
1006         }
1007 }
1008
1009 /*
1010  * Compute the priority of a process when running in user mode.
1011  * Arrange to reschedule if the resulting priority is better
1012  * than that of the current process.
1013  *
1014  * This routine may be called with any process.
1015  *
1016  * This routine is called by fork1() for initial setup with the process
1017  * of the run queue, and also may be called normally with the process on or
1018  * off the run queue.
1019  */
1020 static void
1021 dfly_resetpriority(struct lwp *lp)
1022 {
1023         dfly_pcpu_t rdd;
1024         int newpriority;
1025         u_short newrqtype;
1026         int rcpu;
1027         int checkpri;
1028         int estcpu;
1029         int delta_uload;
1030
1031         crit_enter();
1032
1033         /*
1034          * Lock the scheduler (lp) belongs to.  This can be on a different
1035          * cpu.  Handle races.  This loop breaks out with the appropriate
1036          * rdd locked.
1037          */
1038         for (;;) {
1039                 rcpu = lp->lwp_qcpu;
1040                 cpu_ccfence();
1041                 rdd = &dfly_pcpu[rcpu];
1042                 spin_lock(&rdd->spin);
1043                 if (rcpu == lp->lwp_qcpu)
1044                         break;
1045                 spin_unlock(&rdd->spin);
1046         }
1047
1048         /*
1049          * Calculate the new priority and queue type
1050          */
1051         newrqtype = lp->lwp_rtprio.type;
1052
1053         switch(newrqtype) {
1054         case RTP_PRIO_REALTIME:
1055         case RTP_PRIO_FIFO:
1056                 newpriority = PRIBASE_REALTIME +
1057                              (lp->lwp_rtprio.prio & PRIMASK);
1058                 break;
1059         case RTP_PRIO_NORMAL:
1060                 /*
1061                  *
1062                  */
1063                 estcpu = lp->lwp_estcpu;
1064
1065                 /*
1066                  * p_nice piece         Adds (0-40) * 2         0-80
1067                  * estcpu               Adds 16384  * 4 / 512   0-128
1068                  */
1069                 newpriority = (lp->lwp_proc->p_nice - PRIO_MIN) * PPQ / NICEPPQ;
1070                 newpriority += estcpu * PPQ / ESTCPUPPQ;
1071                 newpriority = newpriority * MAXPRI / (PRIO_RANGE * PPQ /
1072                               NICEPPQ + ESTCPUMAX * PPQ / ESTCPUPPQ);
1073                 newpriority = PRIBASE_NORMAL + (newpriority & PRIMASK);
1074                 break;
1075         case RTP_PRIO_IDLE:
1076                 newpriority = PRIBASE_IDLE + (lp->lwp_rtprio.prio & PRIMASK);
1077                 break;
1078         case RTP_PRIO_THREAD:
1079                 newpriority = PRIBASE_THREAD + (lp->lwp_rtprio.prio & PRIMASK);
1080                 break;
1081         default:
1082                 panic("Bad RTP_PRIO %d", newrqtype);
1083                 /* NOT REACHED */
1084         }
1085
1086         /*
1087          * The LWKT scheduler doesn't dive usched structures, give it a hint
1088          * on the relative priority of user threads running in the kernel.
1089          * The LWKT scheduler will always ensure that a user thread running
1090          * in the kernel will get cpu some time, regardless of its upri,
1091          * but can decide not to instantly switch from one kernel or user
1092          * mode user thread to a kernel-mode user thread when it has a less
1093          * desireable user priority.
1094          *
1095          * td_upri has normal sense (higher values are more desireable), so
1096          * negate it.
1097          */
1098         lp->lwp_thread->td_upri = -(newpriority & usched_dfly_swmask);
1099
1100         /*
1101          * The newpriority incorporates the queue type so do a simple masked
1102          * check to determine if the process has moved to another queue.  If
1103          * it has, and it is currently on a run queue, then move it.
1104          *
1105          * Since uload is ~PPQMASK masked, no modifications are necessary if
1106          * we end up in the same run queue.
1107          */
1108         if ((lp->lwp_priority ^ newpriority) & ~PPQMASK) {
1109                 if (lp->lwp_mpflags & LWP_MP_ONRUNQ) {
1110                         dfly_remrunqueue_locked(rdd, lp);
1111                         lp->lwp_priority = newpriority;
1112                         lp->lwp_rqtype = newrqtype;
1113                         lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ;
1114                         dfly_setrunqueue_locked(rdd, lp);
1115                         checkpri = 1;
1116                 } else {
1117                         lp->lwp_priority = newpriority;
1118                         lp->lwp_rqtype = newrqtype;
1119                         lp->lwp_rqindex = (newpriority & PRIMASK) / PPQ;
1120                         checkpri = 0;
1121                 }
1122         } else {
1123                 /*
1124                  * In the same PPQ, uload cannot change.
1125                  */
1126                 lp->lwp_priority = newpriority;
1127                 checkpri = 1;
1128                 rcpu = -1;
1129         }
1130
1131         /*
1132          * Adjust effective load.
1133          *
1134          * Calculate load then scale up or down geometrically based on p_nice.
1135          * Processes niced up (positive) are less important, and processes
1136          * niced downard (negative) are more important.  The higher the uload,
1137          * the more important the thread.
1138          */
1139         /* 0-511, 0-100% cpu */
1140         delta_uload = lp->lwp_estcpu / NQS;
1141         delta_uload -= delta_uload * lp->lwp_proc->p_nice / (PRIO_MAX + 1);
1142
1143
1144         delta_uload -= lp->lwp_uload;
1145         lp->lwp_uload += delta_uload;
1146         if (lp->lwp_mpflags & LWP_MP_ULOAD)
1147                 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].uload, delta_uload);
1148
1149         /*
1150          * Determine if we need to reschedule the target cpu.  This only
1151          * occurs if the LWP is already on a scheduler queue, which means
1152          * that idle cpu notification has already occured.  At most we
1153          * need only issue a need_user_resched() on the appropriate cpu.
1154          *
1155          * The LWP may be owned by a CPU different from the current one,
1156          * in which case dd->uschedcp may be modified without an MP lock
1157          * or a spinlock held.  The worst that happens is that the code
1158          * below causes a spurious need_user_resched() on the target CPU
1159          * and dd->pri to be wrong for a short period of time, both of
1160          * which are harmless.
1161          *
1162          * If checkpri is 0 we are adjusting the priority of the current
1163          * process, possibly higher (less desireable), so ignore the upri
1164          * check which will fail in that case.
1165          */
1166         if (rcpu >= 0) {
1167                 if ((dfly_rdyprocmask & CPUMASK(rcpu)) &&
1168                     (checkpri == 0 ||
1169                      (rdd->upri & ~PRIMASK) >
1170                      (lp->lwp_priority & ~PRIMASK))) {
1171 #ifdef SMP
1172                         if (rcpu == mycpu->gd_cpuid) {
1173                                 spin_unlock(&rdd->spin);
1174                                 need_user_resched();
1175                         } else {
1176                                 spin_unlock(&rdd->spin);
1177                                 lwkt_send_ipiq(globaldata_find(rcpu),
1178                                                dfly_need_user_resched_remote,
1179                                                NULL);
1180                         }
1181 #else
1182                         spin_unlock(&rdd->spin);
1183                         need_user_resched();
1184 #endif
1185                 } else {
1186                         spin_unlock(&rdd->spin);
1187                 }
1188         } else {
1189                 spin_unlock(&rdd->spin);
1190         }
1191         crit_exit();
1192 }
1193
1194 static
1195 void
1196 dfly_yield(struct lwp *lp)
1197 {
1198 #if 0
1199         /* FUTURE (or something similar) */
1200         switch(lp->lwp_rqtype) {
1201         case RTP_PRIO_NORMAL:
1202                 lp->lwp_estcpu = ESTCPULIM(lp->lwp_estcpu + ESTCPUINCR);
1203                 break;
1204         default:
1205                 break;
1206         }
1207 #endif
1208         need_user_resched();
1209 }
1210
1211 /*
1212  * Called from fork1() when a new child process is being created.
1213  *
1214  * Give the child process an initial estcpu that is more batch then
1215  * its parent and dock the parent for the fork (but do not
1216  * reschedule the parent).
1217  *
1218  * fast
1219  *
1220  * XXX lwp should be "spawning" instead of "forking"
1221  */
1222 static void
1223 dfly_forking(struct lwp *plp, struct lwp *lp)
1224 {
1225         /*
1226          * Put the child 4 queue slots (out of 32) higher than the parent
1227          * (less desireable than the parent).
1228          */
1229         lp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ * 4);
1230         lp->lwp_forked = 1;
1231         lp->lwp_estfast = 0;
1232
1233         /*
1234          * Dock the parent a cost for the fork, protecting us from fork
1235          * bombs.  If the parent is forking quickly make the child more
1236          * batchy.
1237          */
1238         plp->lwp_estcpu = ESTCPULIM(plp->lwp_estcpu + ESTCPUPPQ / 16);
1239 }
1240
1241 /*
1242  * Called when a lwp is being removed from this scheduler, typically
1243  * during lwp_exit().  We have to clean out any ULOAD accounting before
1244  * we can let the lp go.  The dd->spin lock is not needed for uload
1245  * updates.
1246  *
1247  * Scheduler dequeueing has already occurred, no further action in that
1248  * regard is needed.
1249  */
1250 static void
1251 dfly_exiting(struct lwp *lp, struct proc *child_proc)
1252 {
1253         dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu];
1254
1255         if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1256                 atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
1257                 atomic_add_int(&dd->uload, -lp->lwp_uload);
1258                 atomic_add_int(&dd->ucount, -1);
1259                 atomic_add_int(&dfly_ucount, -1);
1260         }
1261 }
1262
1263 /*
1264  * This function cannot block in any way, but spinlocks are ok.
1265  *
1266  * Update the uload based on the state of the thread (whether it is going
1267  * to sleep or running again).  The uload is meant to be a longer-term
1268  * load and not an instantanious load.
1269  */
1270 static void
1271 dfly_uload_update(struct lwp *lp)
1272 {
1273         dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu];
1274
1275         if (lp->lwp_thread->td_flags & TDF_RUNQ) {
1276                 if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) {
1277                         spin_lock(&dd->spin);
1278                         if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) {
1279                                 atomic_set_int(&lp->lwp_mpflags,
1280                                                LWP_MP_ULOAD);
1281                                 atomic_add_int(&dd->uload, lp->lwp_uload);
1282                                 atomic_add_int(&dd->ucount, 1);
1283                                 atomic_add_int(&dfly_ucount, 1);
1284                         }
1285                         spin_unlock(&dd->spin);
1286                 }
1287         } else if (lp->lwp_slptime > 0) {
1288                 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1289                         spin_lock(&dd->spin);
1290                         if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1291                                 atomic_clear_int(&lp->lwp_mpflags,
1292                                                  LWP_MP_ULOAD);
1293                                 atomic_add_int(&dd->uload, -lp->lwp_uload);
1294                                 atomic_add_int(&dd->ucount, -1);
1295                                 atomic_add_int(&dfly_ucount, -1);
1296                         }
1297                         spin_unlock(&dd->spin);
1298                 }
1299         }
1300 }
1301
1302 /*
1303  * chooseproc() is called when a cpu needs a user process to LWKT schedule,
1304  * it selects a user process and returns it.  If chklp is non-NULL and chklp
1305  * has a better or equal priority then the process that would otherwise be
1306  * chosen, NULL is returned.
1307  *
1308  * Until we fix the RUNQ code the chklp test has to be strict or we may
1309  * bounce between processes trying to acquire the current process designation.
1310  *
1311  * Must be called with rdd->spin locked.  The spinlock is left intact through
1312  * the entire routine.  dd->spin does not have to be locked.
1313  *
1314  * If worst is non-zero this function finds the worst thread instead of the
1315  * best thread (used by the schedulerclock-based rover).
1316  */
1317 static
1318 struct lwp *
1319 dfly_chooseproc_locked(dfly_pcpu_t rdd, dfly_pcpu_t dd,
1320                        struct lwp *chklp, int worst)
1321 {
1322         struct lwp *lp;
1323         struct rq *q;
1324         u_int32_t *which, *which2;
1325         u_int32_t pri;
1326         u_int32_t rtqbits;
1327         u_int32_t tsqbits;
1328         u_int32_t idqbits;
1329
1330         rtqbits = rdd->rtqueuebits;
1331         tsqbits = rdd->queuebits;
1332         idqbits = rdd->idqueuebits;
1333
1334         if (worst) {
1335                 if (idqbits) {
1336                         pri = bsrl(idqbits);
1337                         q = &rdd->idqueues[pri];
1338                         which = &rdd->idqueuebits;
1339                         which2 = &idqbits;
1340                 } else if (tsqbits) {
1341                         pri = bsrl(tsqbits);
1342                         q = &rdd->queues[pri];
1343                         which = &rdd->queuebits;
1344                         which2 = &tsqbits;
1345                 } else if (rtqbits) {
1346                         pri = bsrl(rtqbits);
1347                         q = &rdd->rtqueues[pri];
1348                         which = &rdd->rtqueuebits;
1349                         which2 = &rtqbits;
1350                 } else {
1351                         return (NULL);
1352                 }
1353                 lp = TAILQ_LAST(q, rq);
1354         } else {
1355                 if (rtqbits) {
1356                         pri = bsfl(rtqbits);
1357                         q = &rdd->rtqueues[pri];
1358                         which = &rdd->rtqueuebits;
1359                         which2 = &rtqbits;
1360                 } else if (tsqbits) {
1361                         pri = bsfl(tsqbits);
1362                         q = &rdd->queues[pri];
1363                         which = &rdd->queuebits;
1364                         which2 = &tsqbits;
1365                 } else if (idqbits) {
1366                         pri = bsfl(idqbits);
1367                         q = &rdd->idqueues[pri];
1368                         which = &rdd->idqueuebits;
1369                         which2 = &idqbits;
1370                 } else {
1371                         return (NULL);
1372                 }
1373                 lp = TAILQ_FIRST(q);
1374         }
1375         KASSERT(lp, ("chooseproc: no lwp on busy queue"));
1376
1377         /*
1378          * If the passed lwp <chklp> is reasonably close to the selected
1379          * lwp <lp>, return NULL (indicating that <chklp> should be kept).
1380          *
1381          * Note that we must error on the side of <chklp> to avoid bouncing
1382          * between threads in the acquire code.
1383          */
1384         if (chklp) {
1385                 if (chklp->lwp_priority < lp->lwp_priority + PPQ)
1386                         return(NULL);
1387         }
1388
1389         KTR_COND_LOG(usched_chooseproc,
1390             lp->lwp_proc->p_pid == usched_dfly_pid_debug,
1391             lp->lwp_proc->p_pid,
1392             lp->lwp_thread->td_gd->gd_cpuid,
1393             mycpu->gd_cpuid);
1394
1395         KASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) != 0, ("not on runq6!"));
1396         atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
1397         TAILQ_REMOVE(q, lp, lwp_procq);
1398         --rdd->runqcount;
1399         if (TAILQ_EMPTY(q))
1400                 *which &= ~(1 << pri);
1401
1402         /*
1403          * If we are choosing a process from rdd with the intent to
1404          * move it to dd, lwp_qcpu must be adjusted while rdd's spinlock
1405          * is still held.
1406          */
1407         if (rdd != dd) {
1408                 if (lp->lwp_mpflags & LWP_MP_ULOAD) {
1409                         atomic_add_int(&rdd->uload, -lp->lwp_uload);
1410                         atomic_add_int(&rdd->ucount, -1);
1411                         atomic_add_int(&dfly_ucount, -1);
1412                 }
1413                 lp->lwp_qcpu = dd->cpuid;
1414                 atomic_add_int(&dd->uload, lp->lwp_uload);
1415                 atomic_add_int(&dd->ucount, 1);
1416                 atomic_add_int(&dfly_ucount, 1);
1417                 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
1418         }
1419         return lp;
1420 }
1421
1422 #ifdef SMP
1423
1424 /*
1425  * USED TO PUSH RUNNABLE LWPS TO THE LEAST LOADED CPU.
1426  *
1427  * Choose a cpu node to schedule lp on, hopefully nearby its current
1428  * node.
1429  *
1430  * We give the current node a modest advantage for obvious reasons.
1431  *
1432  * We also give the node the thread was woken up FROM a slight advantage
1433  * in order to try to schedule paired threads which synchronize/block waiting
1434  * for each other fairly close to each other.  Similarly in a network setting
1435  * this feature will also attempt to place a user process near the kernel
1436  * protocol thread that is feeding it data.  THIS IS A CRITICAL PART of the
1437  * algorithm as it heuristically groups synchronizing processes for locality
1438  * of reference in multi-socket systems.
1439  *
1440  * We check against running processes and give a big advantage if there
1441  * are none running.
1442  *
1443  * The caller will normally dfly_setrunqueue() lp on the returned queue.
1444  *
1445  * When the topology is known choose a cpu whos group has, in aggregate,
1446  * has the lowest weighted load.
1447  */
1448 static
1449 dfly_pcpu_t
1450 dfly_choose_best_queue(struct lwp *lp)
1451 {
1452         cpumask_t wakemask;
1453         cpumask_t mask;
1454         cpu_node_t *cpup;
1455         cpu_node_t *cpun;
1456         cpu_node_t *cpub;
1457         dfly_pcpu_t dd = &dfly_pcpu[lp->lwp_qcpu];
1458         dfly_pcpu_t rdd;
1459         int wakecpu;
1460         int cpuid;
1461         int n;
1462         int count;
1463         int load;
1464         int lowest_load;
1465
1466         /*
1467          * When the topology is unknown choose a random cpu that is hopefully
1468          * idle.
1469          */
1470         if (dd->cpunode == NULL)
1471                 return (dfly_choose_queue_simple(dd, lp));
1472
1473         /*
1474          * Pairing mask
1475          */
1476         if ((wakecpu = lp->lwp_thread->td_wakefromcpu) >= 0)
1477                 wakemask = dfly_pcpu[wakecpu].cpumask;
1478         else
1479                 wakemask = 0;
1480
1481         /*
1482          * When the topology is known choose a cpu whos group has, in
1483          * aggregate, has the lowest weighted load.
1484          */
1485         cpup = root_cpu_node;
1486         rdd = dd;
1487
1488         while (cpup) {
1489                 /*
1490                  * Degenerate case super-root
1491                  */
1492                 if (cpup->child_node && cpup->child_no == 1) {
1493                         cpup = cpup->child_node;
1494                         continue;
1495                 }
1496
1497                 /*
1498                  * Terminal cpunode
1499                  */
1500                 if (cpup->child_node == NULL) {
1501                         rdd = &dfly_pcpu[BSFCPUMASK(cpup->members)];
1502                         break;
1503                 }
1504
1505                 cpub = NULL;
1506                 lowest_load = 0x7FFFFFFF;
1507
1508                 for (n = 0; n < cpup->child_no; ++n) {
1509                         /*
1510                          * Accumulate load information for all cpus
1511                          * which are members of this node.
1512                          */
1513                         cpun = &cpup->child_node[n];
1514                         mask = cpun->members & usched_global_cpumask &
1515                                smp_active_mask & lp->lwp_cpumask;
1516                         if (mask == 0)
1517                                 continue;
1518
1519                         count = 0;
1520                         load = 0;
1521
1522                         while (mask) {
1523                                 cpuid = BSFCPUMASK(mask);
1524                                 rdd = &dfly_pcpu[cpuid];
1525                                 load += rdd->uload;
1526                                 load += rdd->ucount * usched_dfly_weight3;
1527
1528                                 if (rdd->uschedcp == NULL &&
1529                                     rdd->runqcount == 0 &&
1530                                     globaldata_find(cpuid)->gd_tdrunqcount == 0
1531                                 ) {
1532                                         load -= usched_dfly_weight4;
1533                                 }
1534 #if 0
1535                                 else if (rdd->upri > lp->lwp_priority + PPQ) {
1536                                         load -= usched_dfly_weight4 / 2;
1537                                 }
1538 #endif
1539                                 mask &= ~CPUMASK(cpuid);
1540                                 ++count;
1541                         }
1542
1543                         /*
1544                          * Compensate if the lp is already accounted for in
1545                          * the aggregate uload for this mask set.  We want
1546                          * to calculate the loads as if lp were not present,
1547                          * otherwise the calculation is bogus.
1548                          */
1549                         if ((lp->lwp_mpflags & LWP_MP_ULOAD) &&
1550                             (dd->cpumask & cpun->members)) {
1551                                 load -= lp->lwp_uload;
1552                                 load -= usched_dfly_weight3;
1553                         }
1554
1555                         load /= count;
1556
1557                         /*
1558                          * Advantage the cpu group (lp) is already on.
1559                          */
1560                         if (cpun->members & dd->cpumask)
1561                                 load -= usched_dfly_weight1;
1562
1563                         /*
1564                          * Advantage the cpu group we want to pair (lp) to,
1565                          * but don't let it go to the exact same cpu as
1566                          * the wakecpu target.
1567                          *
1568                          * We do this by checking whether cpun is a
1569                          * terminal node or not.  All cpun's at the same
1570                          * level will either all be terminal or all not
1571                          * terminal.
1572                          *
1573                          * If it is and we match we disadvantage the load.
1574                          * If it is and we don't match we advantage the load.
1575                          *
1576                          * Also note that we are effectively disadvantaging
1577                          * all-but-one by the same amount, so it won't effect
1578                          * the weight1 factor for the all-but-one nodes.
1579                          */
1580                         if (cpun->members & wakemask) {
1581                                 if (cpun->child_node != NULL) {
1582                                         /* advantage */
1583                                         load -= usched_dfly_weight2;
1584                                 } else {
1585                                         if (usched_dfly_features & 0x10)
1586                                                 load += usched_dfly_weight2;
1587                                         else
1588                                                 load -= usched_dfly_weight2;
1589                                 }
1590                         }
1591
1592                         /*
1593                          * Calculate the best load
1594                          */
1595                         if (cpub == NULL || lowest_load > load ||
1596                             (lowest_load == load &&
1597                              (cpun->members & dd->cpumask))
1598                         ) {
1599                                 lowest_load = load;
1600                                 cpub = cpun;
1601                         }
1602                 }
1603                 cpup = cpub;
1604         }
1605         if (usched_dfly_chooser)
1606                 kprintf("lp %02d->%02d %s\n",
1607                         lp->lwp_qcpu, rdd->cpuid, lp->lwp_proc->p_comm);
1608         return (rdd);
1609 }
1610
1611 /*
1612  * USED TO PULL RUNNABLE LWPS FROM THE MOST LOADED CPU.
1613  *
1614  * Choose the worst queue close to dd's cpu node with a non-empty runq
1615  * that is NOT dd.  Also require that the moving of the highest-load thread
1616  * from rdd to dd does not cause the uload's to cross each other.
1617  *
1618  * This is used by the thread chooser when the current cpu's queues are
1619  * empty to steal a thread from another cpu's queue.  We want to offload
1620  * the most heavily-loaded queue.
1621  */
1622 static
1623 dfly_pcpu_t
1624 dfly_choose_worst_queue(dfly_pcpu_t dd)
1625 {
1626         cpumask_t mask;
1627         cpu_node_t *cpup;
1628         cpu_node_t *cpun;
1629         cpu_node_t *cpub;
1630         dfly_pcpu_t rdd;
1631         int cpuid;
1632         int n;
1633         int count;
1634         int load;
1635 #if 0
1636         int pri;
1637         int hpri;
1638 #endif
1639         int highest_load;
1640
1641         /*
1642          * When the topology is unknown choose a random cpu that is hopefully
1643          * idle.
1644          */
1645         if (dd->cpunode == NULL) {
1646                 return (NULL);
1647         }
1648
1649         /*
1650          * When the topology is known choose a cpu whos group has, in
1651          * aggregate, has the lowest weighted load.
1652          */
1653         cpup = root_cpu_node;
1654         rdd = dd;
1655         while (cpup) {
1656                 /*
1657                  * Degenerate case super-root
1658                  */
1659                 if (cpup->child_node && cpup->child_no == 1) {
1660                         cpup = cpup->child_node;
1661                         continue;
1662                 }
1663
1664                 /*
1665                  * Terminal cpunode
1666                  */
1667                 if (cpup->child_node == NULL) {
1668                         rdd = &dfly_pcpu[BSFCPUMASK(cpup->members)];
1669                         break;
1670                 }
1671
1672                 cpub = NULL;
1673                 highest_load = 0;
1674
1675                 for (n = 0; n < cpup->child_no; ++n) {
1676                         /*
1677                          * Accumulate load information for all cpus
1678                          * which are members of this node.
1679                          */
1680                         cpun = &cpup->child_node[n];
1681                         mask = cpun->members & usched_global_cpumask &
1682                                smp_active_mask;
1683                         if (mask == 0)
1684                                 continue;
1685                         count = 0;
1686                         load = 0;
1687
1688                         while (mask) {
1689                                 cpuid = BSFCPUMASK(mask);
1690                                 rdd = &dfly_pcpu[cpuid];
1691                                 load += rdd->uload;
1692                                 load += rdd->ucount * usched_dfly_weight3;
1693                                 if (rdd->uschedcp == NULL &&
1694                                     rdd->runqcount == 0 &&
1695                                     globaldata_find(cpuid)->gd_tdrunqcount == 0
1696                                 ) {
1697                                         load -= usched_dfly_weight4;
1698                                 }
1699 #if 0
1700                                 else if (rdd->upri > dd->upri + PPQ) {
1701                                         load -= usched_dfly_weight4 / 2;
1702                                 }
1703 #endif
1704                                 mask &= ~CPUMASK(cpuid);
1705                                 ++count;
1706                         }
1707                         load /= count;
1708
1709                         /*
1710                          * Prefer candidates which are somewhat closer to
1711                          * our cpu.
1712                          */
1713                         if (dd->cpumask & cpun->members)
1714                                 load += usched_dfly_weight1;
1715
1716                         /*
1717                          * The best candidate is the one with the worst
1718                          * (highest) load.
1719                          */
1720                         if (cpub == NULL || highest_load < load) {
1721                                 highest_load = load;
1722                                 cpub = cpun;
1723                         }
1724                 }
1725                 cpup = cpub;
1726         }
1727
1728         /*
1729          * We never return our own node (dd), and only return a remote
1730          * node if it's load is significantly worse than ours (i.e. where
1731          * stealing a thread would be considered reasonable).
1732          *
1733          * This also helps us avoid breaking paired threads apart which
1734          * can have disastrous effects on performance.
1735          */
1736         if (rdd == dd)
1737                 return(NULL);
1738
1739 #if 0
1740         hpri = 0;
1741         if (rdd->rtqueuebits && hpri < (pri = bsrl(rdd->rtqueuebits)))
1742                 hpri = pri;
1743         if (rdd->queuebits && hpri < (pri = bsrl(rdd->queuebits)))
1744                 hpri = pri;
1745         if (rdd->idqueuebits && hpri < (pri = bsrl(rdd->idqueuebits)))
1746                 hpri = pri;
1747         hpri *= PPQ;
1748         if (rdd->uload - hpri < dd->uload + hpri)
1749                 return(NULL);
1750 #endif
1751         return (rdd);
1752 }
1753
1754 static
1755 dfly_pcpu_t
1756 dfly_choose_queue_simple(dfly_pcpu_t dd, struct lwp *lp)
1757 {
1758         dfly_pcpu_t rdd;
1759         cpumask_t tmpmask;
1760         cpumask_t mask;
1761         int cpuid;
1762
1763         /*
1764          * Fallback to the original heuristic, select random cpu,
1765          * first checking cpus not currently running a user thread.
1766          */
1767         ++dfly_scancpu;
1768         cpuid = (dfly_scancpu & 0xFFFF) % ncpus;
1769         mask = ~dfly_curprocmask & dfly_rdyprocmask & lp->lwp_cpumask &
1770                smp_active_mask & usched_global_cpumask;
1771
1772         while (mask) {
1773                 tmpmask = ~(CPUMASK(cpuid) - 1);
1774                 if (mask & tmpmask)
1775                         cpuid = BSFCPUMASK(mask & tmpmask);
1776                 else
1777                         cpuid = BSFCPUMASK(mask);
1778                 rdd = &dfly_pcpu[cpuid];
1779
1780                 if ((rdd->upri & ~PPQMASK) >= (lp->lwp_priority & ~PPQMASK))
1781                         goto found;
1782                 mask &= ~CPUMASK(cpuid);
1783         }
1784
1785         /*
1786          * Then cpus which might have a currently running lp
1787          */
1788         cpuid = (dfly_scancpu & 0xFFFF) % ncpus;
1789         mask = dfly_curprocmask & dfly_rdyprocmask &
1790                lp->lwp_cpumask & smp_active_mask & usched_global_cpumask;
1791
1792         while (mask) {
1793                 tmpmask = ~(CPUMASK(cpuid) - 1);
1794                 if (mask & tmpmask)
1795                         cpuid = BSFCPUMASK(mask & tmpmask);
1796                 else
1797                         cpuid = BSFCPUMASK(mask);
1798                 rdd = &dfly_pcpu[cpuid];
1799
1800                 if ((rdd->upri & ~PPQMASK) > (lp->lwp_priority & ~PPQMASK))
1801                         goto found;
1802                 mask &= ~CPUMASK(cpuid);
1803         }
1804
1805         /*
1806          * If we cannot find a suitable cpu we reload from dfly_scancpu
1807          * and round-robin.  Other cpus will pickup as they release their
1808          * current lwps or become ready.
1809          *
1810          * Avoid a degenerate system lockup case if usched_global_cpumask
1811          * is set to 0 or otherwise does not cover lwp_cpumask.
1812          *
1813          * We only kick the target helper thread in this case, we do not
1814          * set the user resched flag because
1815          */
1816         cpuid = (dfly_scancpu & 0xFFFF) % ncpus;
1817         if ((CPUMASK(cpuid) & usched_global_cpumask) == 0)
1818                 cpuid = 0;
1819         rdd = &dfly_pcpu[cpuid];
1820 found:
1821         return (rdd);
1822 }
1823
1824 static
1825 void
1826 dfly_need_user_resched_remote(void *dummy)
1827 {
1828         globaldata_t gd = mycpu;
1829         dfly_pcpu_t  dd = &dfly_pcpu[gd->gd_cpuid];
1830
1831         /*
1832          * Flag reschedule needed
1833          */
1834         need_user_resched();
1835
1836         /*
1837          * If no user thread is currently running we need to kick the helper
1838          * on our cpu to recover.  Otherwise the cpu will never schedule
1839          * anything again.
1840          *
1841          * We cannot schedule the process ourselves because this is an
1842          * IPI callback and we cannot acquire spinlocks in an IPI callback.
1843          *
1844          * Call wakeup_mycpu to avoid sending IPIs to other CPUs
1845          */
1846         if (dd->uschedcp == NULL && (dfly_rdyprocmask & gd->gd_cpumask)) {
1847                 atomic_clear_cpumask(&dfly_rdyprocmask, gd->gd_cpumask);
1848                 wakeup_mycpu(&dd->helper_thread);
1849         }
1850 }
1851
1852 #endif
1853
1854 /*
1855  * dfly_remrunqueue_locked() removes a given process from the run queue
1856  * that it is on, clearing the queue busy bit if it becomes empty.
1857  *
1858  * Note that user process scheduler is different from the LWKT schedule.
1859  * The user process scheduler only manages user processes but it uses LWKT
1860  * underneath, and a user process operating in the kernel will often be
1861  * 'released' from our management.
1862  *
1863  * uload is NOT adjusted here.  It is only adjusted if the lwkt_thread goes
1864  * to sleep or the lwp is moved to a different runq.
1865  */
1866 static void
1867 dfly_remrunqueue_locked(dfly_pcpu_t rdd, struct lwp *lp)
1868 {
1869         struct rq *q;
1870         u_int32_t *which;
1871         u_int8_t pri;
1872
1873         KKASSERT(rdd->runqcount >= 0);
1874
1875         pri = lp->lwp_rqindex;
1876
1877         switch(lp->lwp_rqtype) {
1878         case RTP_PRIO_NORMAL:
1879                 q = &rdd->queues[pri];
1880                 which = &rdd->queuebits;
1881                 break;
1882         case RTP_PRIO_REALTIME:
1883         case RTP_PRIO_FIFO:
1884                 q = &rdd->rtqueues[pri];
1885                 which = &rdd->rtqueuebits;
1886                 break;
1887         case RTP_PRIO_IDLE:
1888                 q = &rdd->idqueues[pri];
1889                 which = &rdd->idqueuebits;
1890                 break;
1891         default:
1892                 panic("remrunqueue: invalid rtprio type");
1893                 /* NOT REACHED */
1894         }
1895         KKASSERT(lp->lwp_mpflags & LWP_MP_ONRUNQ);
1896         atomic_clear_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
1897         TAILQ_REMOVE(q, lp, lwp_procq);
1898         --rdd->runqcount;
1899         if (TAILQ_EMPTY(q)) {
1900                 KASSERT((*which & (1 << pri)) != 0,
1901                         ("remrunqueue: remove from empty queue"));
1902                 *which &= ~(1 << pri);
1903         }
1904 }
1905
1906 /*
1907  * dfly_setrunqueue_locked()
1908  *
1909  * Add a process whos rqtype and rqindex had previously been calculated
1910  * onto the appropriate run queue.   Determine if the addition requires
1911  * a reschedule on a cpu and return the cpuid or -1.
1912  *
1913  * NOTE:          Lower priorities are better priorities.
1914  *
1915  * NOTE ON ULOAD: This variable specifies the aggregate load on a cpu, the
1916  *                sum of the rough lwp_priority for all running and runnable
1917  *                processes.  Lower priority processes (higher lwp_priority
1918  *                values) actually DO count as more load, not less, because
1919  *                these are the programs which require the most care with
1920  *                regards to cpu selection.
1921  */
1922 static void
1923 dfly_setrunqueue_locked(dfly_pcpu_t rdd, struct lwp *lp)
1924 {
1925         struct rq *q;
1926         u_int32_t *which;
1927         int pri;
1928
1929         KKASSERT(lp->lwp_qcpu == rdd->cpuid);
1930
1931         if ((lp->lwp_mpflags & LWP_MP_ULOAD) == 0) {
1932                 atomic_set_int(&lp->lwp_mpflags, LWP_MP_ULOAD);
1933                 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].uload, lp->lwp_uload);
1934                 atomic_add_int(&dfly_pcpu[lp->lwp_qcpu].ucount, 1);
1935                 atomic_add_int(&dfly_ucount, 1);
1936         }
1937
1938         pri = lp->lwp_rqindex;
1939
1940         switch(lp->lwp_rqtype) {
1941         case RTP_PRIO_NORMAL:
1942                 q = &rdd->queues[pri];
1943                 which = &rdd->queuebits;
1944                 break;
1945         case RTP_PRIO_REALTIME:
1946         case RTP_PRIO_FIFO:
1947                 q = &rdd->rtqueues[pri];
1948                 which = &rdd->rtqueuebits;
1949                 break;
1950         case RTP_PRIO_IDLE:
1951                 q = &rdd->idqueues[pri];
1952                 which = &rdd->idqueuebits;
1953                 break;
1954         default:
1955                 panic("remrunqueue: invalid rtprio type");
1956                 /* NOT REACHED */
1957         }
1958
1959         /*
1960          * Place us on the selected queue.  Determine if we should be
1961          * placed at the head of the queue or at the end.
1962          *
1963          * We are placed at the tail if our round-robin count has expired,
1964          * or is about to expire and the system thinks its a good place to
1965          * round-robin, or there is already a next thread on the queue
1966          * (it might be trying to pick up where it left off and we don't
1967          * want to interfere).
1968          */
1969         KKASSERT((lp->lwp_mpflags & LWP_MP_ONRUNQ) == 0);
1970         atomic_set_int(&lp->lwp_mpflags, LWP_MP_ONRUNQ);
1971         ++rdd->runqcount;
1972
1973         if (lp->lwp_rrcount >= usched_dfly_rrinterval ||
1974             (lp->lwp_rrcount >= usched_dfly_rrinterval / 2 &&
1975              (lp->lwp_thread->td_mpflags & TDF_MP_BATCH_DEMARC)) ||
1976             !TAILQ_EMPTY(q)
1977         ) {
1978                 atomic_clear_int(&lp->lwp_thread->td_mpflags,
1979                                  TDF_MP_BATCH_DEMARC);
1980                 lp->lwp_rrcount = 0;
1981                 TAILQ_INSERT_TAIL(q, lp, lwp_procq);
1982         } else {
1983                 if (TAILQ_EMPTY(q))
1984                         lp->lwp_rrcount = 0;
1985                 TAILQ_INSERT_HEAD(q, lp, lwp_procq);
1986         }
1987         *which |= 1 << pri;
1988 }
1989
1990 #ifdef SMP
1991
1992 /*
1993  * For SMP systems a user scheduler helper thread is created for each
1994  * cpu and is used to allow one cpu to wakeup another for the purposes of
1995  * scheduling userland threads from setrunqueue().
1996  *
1997  * UP systems do not need the helper since there is only one cpu.
1998  *
1999  * We can't use the idle thread for this because we might block.
2000  * Additionally, doing things this way allows us to HLT idle cpus
2001  * on MP systems.
2002  */
2003 static void
2004 dfly_helper_thread(void *dummy)
2005 {
2006     globaldata_t gd;
2007     dfly_pcpu_t dd;
2008     dfly_pcpu_t rdd;
2009     struct lwp *nlp;
2010     cpumask_t mask;
2011     int cpuid;
2012
2013     gd = mycpu;
2014     cpuid = gd->gd_cpuid;       /* doesn't change */
2015     mask = gd->gd_cpumask;      /* doesn't change */
2016     dd = &dfly_pcpu[cpuid];
2017
2018     /*
2019      * Since we only want to be woken up only when no user processes
2020      * are scheduled on a cpu, run at an ultra low priority.
2021      */
2022     lwkt_setpri_self(TDPRI_USER_SCHEDULER);
2023
2024     tsleep(&dd->helper_thread, 0, "schslp", 0);
2025
2026     for (;;) {
2027         /*
2028          * We use the LWKT deschedule-interlock trick to avoid racing
2029          * dfly_rdyprocmask.  This means we cannot block through to the
2030          * manual lwkt_switch() call we make below.
2031          */
2032         crit_enter_gd(gd);
2033         tsleep_interlock(&dd->helper_thread, 0);
2034
2035         spin_lock(&dd->spin);
2036
2037         atomic_set_cpumask(&dfly_rdyprocmask, mask);
2038         clear_user_resched();   /* This satisfied the reschedule request */
2039 #if 0
2040         dd->rrcount = 0;        /* Reset the round-robin counter */
2041 #endif
2042
2043         if (dd->runqcount || dd->uschedcp != NULL) {
2044                 /*
2045                  * Threads are available.  A thread may or may not be
2046                  * currently scheduled.  Get the best thread already queued
2047                  * to this cpu.
2048                  */
2049                 nlp = dfly_chooseproc_locked(dd, dd, dd->uschedcp, 0);
2050                 if (nlp) {
2051                         atomic_set_cpumask(&dfly_curprocmask, mask);
2052                         dd->upri = nlp->lwp_priority;
2053                         dd->uschedcp = nlp;
2054 #if 0
2055                         dd->rrcount = 0;        /* reset round robin */
2056 #endif
2057                         spin_unlock(&dd->spin);
2058                         lwkt_acquire(nlp->lwp_thread);
2059                         lwkt_schedule(nlp->lwp_thread);
2060                 } else {
2061                         /*
2062                          * This situation should not occur because we had
2063                          * at least one thread available.
2064                          */
2065                         spin_unlock(&dd->spin);
2066                 }
2067         } else if (usched_dfly_features & 0x01) {
2068                 /*
2069                  * This cpu is devoid of runnable threads, steal a thread
2070                  * from another cpu.  Since we're stealing, might as well
2071                  * load balance at the same time.
2072                  *
2073                  * We choose the highest-loaded thread from the worst queue.
2074                  *
2075                  * NOTE! This function only returns a non-NULL rdd when
2076                  *       another cpu's queue is obviously overloaded.  We
2077                  *       do not want to perform the type of rebalancing
2078                  *       the schedclock does here because it would result
2079                  *       in insane process pulling when 'steady' state is
2080                  *       partially unbalanced (e.g. 6 runnables and only
2081                  *       4 cores).
2082                  */
2083                 rdd = dfly_choose_worst_queue(dd);
2084                 if (rdd && spin_trylock(&rdd->spin)) {
2085                         nlp = dfly_chooseproc_locked(rdd, dd, NULL, 1);
2086                         spin_unlock(&rdd->spin);
2087                 } else {
2088                         nlp = NULL;
2089                 }
2090                 if (nlp) {
2091                         atomic_set_cpumask(&dfly_curprocmask, mask);
2092                         dd->upri = nlp->lwp_priority;
2093                         dd->uschedcp = nlp;
2094 #if 0
2095                         dd->rrcount = 0;        /* reset round robin */
2096 #endif
2097                         spin_unlock(&dd->spin);
2098                         lwkt_acquire(nlp->lwp_thread);
2099                         lwkt_schedule(nlp->lwp_thread);
2100                 } else {
2101                         /*
2102                          * Leave the thread on our run queue.  Another
2103                          * scheduler will try to pull it later.
2104                          */
2105                         spin_unlock(&dd->spin);
2106                 }
2107         } else {
2108                 /*
2109                  * devoid of runnable threads and not allowed to steal
2110                  * any.
2111                  */
2112                 spin_unlock(&dd->spin);
2113         }
2114
2115         /*
2116          * We're descheduled unless someone scheduled us.  Switch away.
2117          * Exiting the critical section will cause splz() to be called
2118          * for us if interrupts and such are pending.
2119          */
2120         crit_exit_gd(gd);
2121         tsleep(&dd->helper_thread, PINTERLOCKED, "schslp", 0);
2122     }
2123 }
2124
2125 #if 0
2126 static int
2127 sysctl_usched_dfly_stick_to_level(SYSCTL_HANDLER_ARGS)
2128 {
2129         int error, new_val;
2130
2131         new_val = usched_dfly_stick_to_level;
2132
2133         error = sysctl_handle_int(oidp, &new_val, 0, req);
2134         if (error != 0 || req->newptr == NULL)
2135                 return (error);
2136         if (new_val > cpu_topology_levels_number - 1 || new_val < 0)
2137                 return (EINVAL);
2138         usched_dfly_stick_to_level = new_val;
2139         return (0);
2140 }
2141 #endif
2142
2143 /*
2144  * Setup our scheduler helpers.  Note that curprocmask bit 0 has already
2145  * been cleared by rqinit() and we should not mess with it further.
2146  */
2147 static void
2148 dfly_helper_thread_cpu_init(void)
2149 {
2150         int i;
2151         int j;
2152         int cpuid;
2153         int smt_not_supported = 0;
2154         int cache_coherent_not_supported = 0;
2155
2156         if (bootverbose)
2157                 kprintf("Start scheduler helpers on cpus:\n");
2158
2159         sysctl_ctx_init(&usched_dfly_sysctl_ctx);
2160         usched_dfly_sysctl_tree =
2161                 SYSCTL_ADD_NODE(&usched_dfly_sysctl_ctx,
2162                                 SYSCTL_STATIC_CHILDREN(_kern), OID_AUTO,
2163                                 "usched_dfly", CTLFLAG_RD, 0, "");
2164
2165         for (i = 0; i < ncpus; ++i) {
2166                 dfly_pcpu_t dd = &dfly_pcpu[i];
2167                 cpumask_t mask = CPUMASK(i);
2168
2169                 if ((mask & smp_active_mask) == 0)
2170                     continue;
2171
2172                 spin_init(&dd->spin);
2173                 dd->cpunode = get_cpu_node_by_cpuid(i);
2174                 dd->cpuid = i;
2175                 dd->cpumask = CPUMASK(i);
2176                 for (j = 0; j < NQS; j++) {
2177                         TAILQ_INIT(&dd->queues[j]);
2178                         TAILQ_INIT(&dd->rtqueues[j]);
2179                         TAILQ_INIT(&dd->idqueues[j]);
2180                 }
2181                 atomic_clear_cpumask(&dfly_curprocmask, 1);
2182
2183                 if (dd->cpunode == NULL) {
2184                         smt_not_supported = 1;
2185                         cache_coherent_not_supported = 1;
2186                         if (bootverbose)
2187                                 kprintf ("\tcpu%d - WARNING: No CPU NODE "
2188                                          "found for cpu\n", i);
2189                 } else {
2190                         switch (dd->cpunode->type) {
2191                         case THREAD_LEVEL:
2192                                 if (bootverbose)
2193                                         kprintf ("\tcpu%d - HyperThreading "
2194                                                  "available. Core siblings: ",
2195                                                  i);
2196                                 break;
2197                         case CORE_LEVEL:
2198                                 smt_not_supported = 1;
2199
2200                                 if (bootverbose)
2201                                         kprintf ("\tcpu%d - No HT available, "
2202                                                  "multi-core/physical "
2203                                                  "cpu. Physical siblings: ",
2204                                                  i);
2205                                 break;
2206                         case CHIP_LEVEL:
2207                                 smt_not_supported = 1;
2208
2209                                 if (bootverbose)
2210                                         kprintf ("\tcpu%d - No HT available, "
2211                                                  "single-core/physical cpu. "
2212                                                  "Package Siblings: ",
2213                                                  i);
2214                                 break;
2215                         default:
2216                                 /* Let's go for safe defaults here */
2217                                 smt_not_supported = 1;
2218                                 cache_coherent_not_supported = 1;
2219                                 if (bootverbose)
2220                                         kprintf ("\tcpu%d - Unknown cpunode->"
2221                                                  "type=%u. Siblings: ",
2222                                                  i,
2223                                                  (u_int)dd->cpunode->type);
2224                                 break;
2225                         }
2226
2227                         if (bootverbose) {
2228                                 if (dd->cpunode->parent_node != NULL) {
2229                                         CPUSET_FOREACH(cpuid, dd->cpunode->parent_node->members)
2230                                                 kprintf("cpu%d ", cpuid);
2231                                         kprintf("\n");
2232                                 } else {
2233                                         kprintf(" no siblings\n");
2234                                 }
2235                         }
2236                 }
2237
2238                 lwkt_create(dfly_helper_thread, NULL, NULL, &dd->helper_thread,
2239                             0, i, "usched %d", i);
2240
2241                 /*
2242                  * Allow user scheduling on the target cpu.  cpu #0 has already
2243                  * been enabled in rqinit().
2244                  */
2245                 if (i)
2246                     atomic_clear_cpumask(&dfly_curprocmask, mask);
2247                 atomic_set_cpumask(&dfly_rdyprocmask, mask);
2248                 dd->upri = PRIBASE_NULL;
2249
2250         }
2251
2252         /* usched_dfly sysctl configurable parameters */
2253
2254         SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2255                        SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2256                        OID_AUTO, "rrinterval", CTLFLAG_RW,
2257                        &usched_dfly_rrinterval, 0, "");
2258         SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2259                        SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2260                        OID_AUTO, "decay", CTLFLAG_RW,
2261                        &usched_dfly_decay, 0, "Extra decay when not running");
2262
2263         /* Add enable/disable option for SMT scheduling if supported */
2264         if (smt_not_supported) {
2265                 usched_dfly_smt = 0;
2266                 SYSCTL_ADD_STRING(&usched_dfly_sysctl_ctx,
2267                                   SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2268                                   OID_AUTO, "smt", CTLFLAG_RD,
2269                                   "NOT SUPPORTED", 0, "SMT NOT SUPPORTED");
2270         } else {
2271                 usched_dfly_smt = 1;
2272                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2273                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2274                                OID_AUTO, "smt", CTLFLAG_RW,
2275                                &usched_dfly_smt, 0, "Enable SMT scheduling");
2276         }
2277
2278         /*
2279          * Add enable/disable option for cache coherent scheduling
2280          * if supported
2281          */
2282         if (cache_coherent_not_supported) {
2283                 usched_dfly_cache_coherent = 0;
2284                 SYSCTL_ADD_STRING(&usched_dfly_sysctl_ctx,
2285                                   SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2286                                   OID_AUTO, "cache_coherent", CTLFLAG_RD,
2287                                   "NOT SUPPORTED", 0,
2288                                   "Cache coherence NOT SUPPORTED");
2289         } else {
2290                 usched_dfly_cache_coherent = 1;
2291                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2292                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2293                                OID_AUTO, "cache_coherent", CTLFLAG_RW,
2294                                &usched_dfly_cache_coherent, 0,
2295                                "Enable/Disable cache coherent scheduling");
2296
2297                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2298                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2299                                OID_AUTO, "weight1", CTLFLAG_RW,
2300                                &usched_dfly_weight1, 200,
2301                                "Weight selection for current cpu");
2302
2303                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2304                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2305                                OID_AUTO, "weight2", CTLFLAG_RW,
2306                                &usched_dfly_weight2, 180,
2307                                "Weight selection for wakefrom cpu");
2308
2309                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2310                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2311                                OID_AUTO, "weight3", CTLFLAG_RW,
2312                                &usched_dfly_weight3, 40,
2313                                "Weight selection for num threads on queue");
2314
2315                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2316                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2317                                OID_AUTO, "weight4", CTLFLAG_RW,
2318                                &usched_dfly_weight4, 160,
2319                                "Availability of other idle cpus");
2320
2321                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2322                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2323                                OID_AUTO, "fast_resched", CTLFLAG_RW,
2324                                &usched_dfly_fast_resched, 0,
2325                                "Availability of other idle cpus");
2326
2327                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2328                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2329                                OID_AUTO, "features", CTLFLAG_RW,
2330                                &usched_dfly_features, 0x8F,
2331                                "Allow pulls into empty queues");
2332
2333                 SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2334                                SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2335                                OID_AUTO, "swmask", CTLFLAG_RW,
2336                                &usched_dfly_swmask, ~PPQMASK,
2337                                "Queue mask to force thread switch");
2338
2339
2340 #if 0
2341                 SYSCTL_ADD_PROC(&usched_dfly_sysctl_ctx,
2342                                 SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2343                                 OID_AUTO, "stick_to_level",
2344                                 CTLTYPE_INT | CTLFLAG_RW,
2345                                 NULL, sizeof usched_dfly_stick_to_level,
2346                                 sysctl_usched_dfly_stick_to_level, "I",
2347                                 "Stick a process to this level. See sysctl"
2348                                 "paremter hw.cpu_topology.level_description");
2349 #endif
2350         }
2351 }
2352 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND,
2353         dfly_helper_thread_cpu_init, NULL)
2354
2355 #else /* No SMP options - just add the configurable parameters to sysctl */
2356
2357 static void
2358 sched_sysctl_tree_init(void)
2359 {
2360         sysctl_ctx_init(&usched_dfly_sysctl_ctx);
2361         usched_dfly_sysctl_tree =
2362                 SYSCTL_ADD_NODE(&usched_dfly_sysctl_ctx,
2363                                 SYSCTL_STATIC_CHILDREN(_kern), OID_AUTO,
2364                                 "usched_dfly", CTLFLAG_RD, 0, "");
2365
2366         /* usched_dfly sysctl configurable parameters */
2367         SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2368                        SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2369                        OID_AUTO, "rrinterval", CTLFLAG_RW,
2370                        &usched_dfly_rrinterval, 0, "");
2371         SYSCTL_ADD_INT(&usched_dfly_sysctl_ctx,
2372                        SYSCTL_CHILDREN(usched_dfly_sysctl_tree),
2373                        OID_AUTO, "decay", CTLFLAG_RW,
2374                        &usched_dfly_decay, 0, "Extra decay when not running");
2375 }
2376 SYSINIT(uschedtd, SI_BOOT2_USCHED, SI_ORDER_SECOND,
2377         sched_sysctl_tree_init, NULL)
2378 #endif