xref: /freebsd/sys/kern/sched_ule.c (revision ebccf1e3a6b11b97cbf5f813dd76636e892a9035)
135e6168fSJeff Roberson /*-
215dc847eSJeff Roberson  * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org>
335e6168fSJeff Roberson  * All rights reserved.
435e6168fSJeff Roberson  *
535e6168fSJeff Roberson  * Redistribution and use in source and binary forms, with or without
635e6168fSJeff Roberson  * modification, are permitted provided that the following conditions
735e6168fSJeff Roberson  * are met:
835e6168fSJeff Roberson  * 1. Redistributions of source code must retain the above copyright
935e6168fSJeff Roberson  *    notice unmodified, this list of conditions, and the following
1035e6168fSJeff Roberson  *    disclaimer.
1135e6168fSJeff Roberson  * 2. Redistributions in binary form must reproduce the above copyright
1235e6168fSJeff Roberson  *    notice, this list of conditions and the following disclaimer in the
1335e6168fSJeff Roberson  *    documentation and/or other materials provided with the distribution.
1435e6168fSJeff Roberson  *
1535e6168fSJeff Roberson  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1635e6168fSJeff Roberson  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1735e6168fSJeff Roberson  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
1835e6168fSJeff Roberson  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
1935e6168fSJeff Roberson  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
2035e6168fSJeff Roberson  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2135e6168fSJeff Roberson  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2235e6168fSJeff Roberson  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2335e6168fSJeff Roberson  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
2435e6168fSJeff Roberson  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2535e6168fSJeff Roberson  */
2635e6168fSJeff Roberson 
27677b542eSDavid E. O'Brien #include <sys/cdefs.h>
28677b542eSDavid E. O'Brien __FBSDID("$FreeBSD$");
29677b542eSDavid E. O'Brien 
309923b511SScott Long #include <opt_sched.h>
319923b511SScott Long 
32ed062c8dSJulian Elischer #define kse td_sched
33ed062c8dSJulian Elischer 
3435e6168fSJeff Roberson #include <sys/param.h>
3535e6168fSJeff Roberson #include <sys/systm.h>
362c3490b1SMarcel Moolenaar #include <sys/kdb.h>
3735e6168fSJeff Roberson #include <sys/kernel.h>
3835e6168fSJeff Roberson #include <sys/ktr.h>
3935e6168fSJeff Roberson #include <sys/lock.h>
4035e6168fSJeff Roberson #include <sys/mutex.h>
4135e6168fSJeff Roberson #include <sys/proc.h>
42245f3abfSJeff Roberson #include <sys/resource.h>
439bacd788SJeff Roberson #include <sys/resourcevar.h>
4435e6168fSJeff Roberson #include <sys/sched.h>
4535e6168fSJeff Roberson #include <sys/smp.h>
4635e6168fSJeff Roberson #include <sys/sx.h>
4735e6168fSJeff Roberson #include <sys/sysctl.h>
4835e6168fSJeff Roberson #include <sys/sysproto.h>
49f5c157d9SJohn Baldwin #include <sys/turnstile.h>
5035e6168fSJeff Roberson #include <sys/vmmeter.h>
5135e6168fSJeff Roberson #ifdef KTRACE
5235e6168fSJeff Roberson #include <sys/uio.h>
5335e6168fSJeff Roberson #include <sys/ktrace.h>
5435e6168fSJeff Roberson #endif
5535e6168fSJeff Roberson 
56ebccf1e3SJoseph Koshy #ifdef HWPMC_HOOKS
57ebccf1e3SJoseph Koshy #include <sys/pmckern.h>
58ebccf1e3SJoseph Koshy #endif
59ebccf1e3SJoseph Koshy 
6035e6168fSJeff Roberson #include <machine/cpu.h>
6122bf7d9aSJeff Roberson #include <machine/smp.h>
6235e6168fSJeff Roberson 
6335e6168fSJeff Roberson /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
6435e6168fSJeff Roberson /* XXX This is bogus compatability crap for ps */
6535e6168fSJeff Roberson static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
6635e6168fSJeff Roberson SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
6735e6168fSJeff Roberson 
6835e6168fSJeff Roberson static void sched_setup(void *dummy);
6935e6168fSJeff Roberson SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
7035e6168fSJeff Roberson 
71e038d354SScott Long static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "Scheduler");
72e1f89c22SJeff Roberson 
73e038d354SScott Long SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "ule", 0,
74e038d354SScott Long     "Scheduler name");
75dc095794SScott Long 
7615dc847eSJeff Roberson static int slice_min = 1;
7715dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, "");
7815dc847eSJeff Roberson 
79210491d3SJeff Roberson static int slice_max = 10;
8015dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, "");
8115dc847eSJeff Roberson 
8215dc847eSJeff Roberson int realstathz;
8315dc847eSJeff Roberson int tickincr = 1;
84783caefbSJeff Roberson 
8535e6168fSJeff Roberson /*
86ed062c8dSJulian Elischer  * The schedulable entity that can be given a context to run.
87ed062c8dSJulian Elischer  * A process may have several of these. Probably one per processor
88ed062c8dSJulian Elischer  * but posibly a few more. In this universe they are grouped
89ed062c8dSJulian Elischer  * with a KSEG that contains the priority and niceness
90ed062c8dSJulian Elischer  * for the group.
91ed062c8dSJulian Elischer  */
92ed062c8dSJulian Elischer struct kse {
93ed062c8dSJulian Elischer 	TAILQ_ENTRY(kse) ke_procq;	/* (j/z) Run queue. */
94ed062c8dSJulian Elischer 	int		ke_flags;	/* (j) KEF_* flags. */
95ed062c8dSJulian Elischer 	struct thread	*ke_thread;	/* (*) Active associated thread. */
96ed062c8dSJulian Elischer 	fixpt_t		ke_pctcpu;	/* (j) %cpu during p_swtime. */
97ed062c8dSJulian Elischer 	char		ke_rqindex;	/* (j) Run queue index. */
98ed062c8dSJulian Elischer 	enum {
99ed062c8dSJulian Elischer 		KES_THREAD = 0x0,	/* slaved to thread state */
100ed062c8dSJulian Elischer 		KES_ONRUNQ
101ed062c8dSJulian Elischer 	} ke_state;			/* (j) thread sched specific status. */
102ed062c8dSJulian Elischer 	int		ke_slptime;
103ed062c8dSJulian Elischer 	int		ke_slice;
104ed062c8dSJulian Elischer 	struct runq	*ke_runq;
105ed062c8dSJulian Elischer 	u_char		ke_cpu;		/* CPU that we have affinity for. */
106ed062c8dSJulian Elischer 	/* The following variables are only used for pctcpu calculation */
107ed062c8dSJulian Elischer 	int		ke_ltick;	/* Last tick that we were running on */
108ed062c8dSJulian Elischer 	int		ke_ftick;	/* First tick that we were running on */
109ed062c8dSJulian Elischer 	int		ke_ticks;	/* Tick count */
110ed062c8dSJulian Elischer 
111ed062c8dSJulian Elischer };
112ed062c8dSJulian Elischer 
113ed062c8dSJulian Elischer 
114ed062c8dSJulian Elischer #define td_kse td_sched
115ed062c8dSJulian Elischer #define	td_slptime		td_kse->ke_slptime
116ed062c8dSJulian Elischer #define ke_proc			ke_thread->td_proc
117ed062c8dSJulian Elischer #define ke_ksegrp		ke_thread->td_ksegrp
118ed062c8dSJulian Elischer 
119ed062c8dSJulian Elischer /* flags kept in ke_flags */
120ed062c8dSJulian Elischer #define	KEF_SCHED0	0x00001	/* For scheduler-specific use. */
121ed062c8dSJulian Elischer #define	KEF_SCHED1	0x00002	/* For scheduler-specific use. */
122ed062c8dSJulian Elischer #define	KEF_SCHED2	0x00004	/* For scheduler-specific use. */
123ed062c8dSJulian Elischer #define	KEF_SCHED3	0x00008	/* For scheduler-specific use. */
1242d59a44dSJeff Roberson #define	KEF_SCHED4	0x00010
1258ffb8f55SJeff Roberson #define	KEF_SCHED5	0x00020
126ed062c8dSJulian Elischer #define	KEF_DIDRUN	0x02000	/* Thread actually ran. */
127ed062c8dSJulian Elischer #define	KEF_EXIT	0x04000	/* Thread is being killed. */
128ed062c8dSJulian Elischer 
129ed062c8dSJulian Elischer /*
13035e6168fSJeff Roberson  * These datastructures are allocated within their parent datastructure but
13135e6168fSJeff Roberson  * are scheduler specific.
13235e6168fSJeff Roberson  */
13335e6168fSJeff Roberson 
13422bf7d9aSJeff Roberson #define	ke_assign	ke_procq.tqe_next
13522bf7d9aSJeff Roberson 
136598b368dSJeff Roberson #define	KEF_ASSIGNED	0x0001		/* Thread is being migrated. */
137598b368dSJeff Roberson #define	KEF_BOUND	0x0002		/* Thread can not migrate. */
138598b368dSJeff Roberson #define	KEF_XFERABLE	0x0004		/* Thread was added as transferable. */
139598b368dSJeff Roberson #define	KEF_HOLD	0x0008		/* Thread is temporarily bound. */
140598b368dSJeff Roberson #define	KEF_REMOVED	0x0010		/* Thread was removed while ASSIGNED */
141f5c157d9SJohn Baldwin #define	KEF_INTERNAL	0x0020
14235e6168fSJeff Roberson 
14335e6168fSJeff Roberson struct kg_sched {
144ed062c8dSJulian Elischer 	struct thread	*skg_last_assigned; /* (j) Last thread assigned to */
145ed062c8dSJulian Elischer 					   /* the system scheduler */
146407b0157SJeff Roberson 	int	skg_slptime;		/* Number of ticks we vol. slept */
147407b0157SJeff Roberson 	int	skg_runtime;		/* Number of ticks we were running */
148ed062c8dSJulian Elischer 	int	skg_avail_opennings;	/* (j) Num unfilled slots in group.*/
149ed062c8dSJulian Elischer 	int	skg_concurrency;	/* (j) Num threads requested in group.*/
15035e6168fSJeff Roberson };
151ed062c8dSJulian Elischer #define kg_last_assigned	kg_sched->skg_last_assigned
152ed062c8dSJulian Elischer #define kg_avail_opennings	kg_sched->skg_avail_opennings
153ed062c8dSJulian Elischer #define kg_concurrency		kg_sched->skg_concurrency
154407b0157SJeff Roberson #define kg_runtime		kg_sched->skg_runtime
155ed062c8dSJulian Elischer #define kg_slptime		kg_sched->skg_slptime
15635e6168fSJeff Roberson 
157d39063f2SJulian Elischer #define SLOT_RELEASE(kg)						\
158d39063f2SJulian Elischer do {									\
159d39063f2SJulian Elischer 	kg->kg_avail_opennings++; 					\
160d39063f2SJulian Elischer 	CTR3(KTR_RUNQ, "kg %p(%d) Slot released (->%d)",		\
161d39063f2SJulian Elischer 	kg,								\
162d39063f2SJulian Elischer 	kg->kg_concurrency,						\
163d39063f2SJulian Elischer 	 kg->kg_avail_opennings);					\
164d39063f2SJulian Elischer 	/*KASSERT((kg->kg_avail_opennings <= kg->kg_concurrency),	\
165d39063f2SJulian Elischer 	    ("slots out of whack")); */					\
166d39063f2SJulian Elischer } while (0)
167d39063f2SJulian Elischer 
168d39063f2SJulian Elischer #define SLOT_USE(kg)							\
169d39063f2SJulian Elischer do {									\
170d39063f2SJulian Elischer 	kg->kg_avail_opennings--; 					\
171d39063f2SJulian Elischer 	CTR3(KTR_RUNQ, "kg %p(%d) Slot used (->%d)",			\
172d39063f2SJulian Elischer 	kg,								\
173d39063f2SJulian Elischer 	kg->kg_concurrency,						\
174d39063f2SJulian Elischer 	 kg->kg_avail_opennings);					\
175d39063f2SJulian Elischer 	/*KASSERT((kg->kg_avail_opennings >= 0),			\
176d39063f2SJulian Elischer 	    ("slots out of whack"));*/ 					\
177d39063f2SJulian Elischer } while (0)
178d39063f2SJulian Elischer 
179ed062c8dSJulian Elischer static struct kse kse0;
180ed062c8dSJulian Elischer static struct kg_sched kg_sched0;
18135e6168fSJeff Roberson 
18235e6168fSJeff Roberson /*
183665cb285SJeff Roberson  * The priority is primarily determined by the interactivity score.  Thus, we
184665cb285SJeff Roberson  * give lower(better) priorities to kse groups that use less CPU.  The nice
185665cb285SJeff Roberson  * value is then directly added to this to allow nice to have some effect
186665cb285SJeff Roberson  * on latency.
187e1f89c22SJeff Roberson  *
188e1f89c22SJeff Roberson  * PRI_RANGE:	Total priority range for timeshare threads.
189665cb285SJeff Roberson  * PRI_NRESV:	Number of nice values.
190e1f89c22SJeff Roberson  * PRI_BASE:	The start of the dynamic range.
19135e6168fSJeff Roberson  */
192407b0157SJeff Roberson #define	SCHED_PRI_RANGE		(PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
193a0a931ceSJeff Roberson #define	SCHED_PRI_NRESV		((PRIO_MAX - PRIO_MIN) + 1)
194a0a931ceSJeff Roberson #define	SCHED_PRI_NHALF		(SCHED_PRI_NRESV / 2)
195665cb285SJeff Roberson #define	SCHED_PRI_BASE		(PRI_MIN_TIMESHARE)
19615dc847eSJeff Roberson #define	SCHED_PRI_INTERACT(score)					\
197665cb285SJeff Roberson     ((score) * SCHED_PRI_RANGE / SCHED_INTERACT_MAX)
19835e6168fSJeff Roberson 
19935e6168fSJeff Roberson /*
200e1f89c22SJeff Roberson  * These determine the interactivity of a process.
20135e6168fSJeff Roberson  *
202407b0157SJeff Roberson  * SLP_RUN_MAX:	Maximum amount of sleep time + run time we'll accumulate
203407b0157SJeff Roberson  *		before throttling back.
204d322132cSJeff Roberson  * SLP_RUN_FORK:	Maximum slp+run time to inherit at fork time.
205210491d3SJeff Roberson  * INTERACT_MAX:	Maximum interactivity value.  Smaller is better.
206e1f89c22SJeff Roberson  * INTERACT_THRESH:	Threshhold for placement on the current runq.
20735e6168fSJeff Roberson  */
2084c9612c6SJeff Roberson #define	SCHED_SLP_RUN_MAX	((hz * 5) << 10)
209d322132cSJeff Roberson #define	SCHED_SLP_RUN_FORK	((hz / 2) << 10)
210210491d3SJeff Roberson #define	SCHED_INTERACT_MAX	(100)
211210491d3SJeff Roberson #define	SCHED_INTERACT_HALF	(SCHED_INTERACT_MAX / 2)
2124c9612c6SJeff Roberson #define	SCHED_INTERACT_THRESH	(30)
213e1f89c22SJeff Roberson 
21435e6168fSJeff Roberson /*
21535e6168fSJeff Roberson  * These parameters and macros determine the size of the time slice that is
21635e6168fSJeff Roberson  * granted to each thread.
21735e6168fSJeff Roberson  *
21835e6168fSJeff Roberson  * SLICE_MIN:	Minimum time slice granted, in units of ticks.
21935e6168fSJeff Roberson  * SLICE_MAX:	Maximum time slice granted.
22035e6168fSJeff Roberson  * SLICE_RANGE:	Range of available time slices scaled by hz.
221245f3abfSJeff Roberson  * SLICE_SCALE:	The number slices granted per val in the range of [0, max].
222245f3abfSJeff Roberson  * SLICE_NICE:  Determine the amount of slice granted to a scaled nice.
2237d1a81b4SJeff Roberson  * SLICE_NTHRESH:	The nice cutoff point for slice assignment.
22435e6168fSJeff Roberson  */
22515dc847eSJeff Roberson #define	SCHED_SLICE_MIN			(slice_min)
22615dc847eSJeff Roberson #define	SCHED_SLICE_MAX			(slice_max)
2270392e39dSJeff Roberson #define	SCHED_SLICE_INTERACTIVE		(slice_max)
2287d1a81b4SJeff Roberson #define	SCHED_SLICE_NTHRESH	(SCHED_PRI_NHALF - 1)
22935e6168fSJeff Roberson #define	SCHED_SLICE_RANGE		(SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1)
23035e6168fSJeff Roberson #define	SCHED_SLICE_SCALE(val, max)	(((val) * SCHED_SLICE_RANGE) / (max))
231245f3abfSJeff Roberson #define	SCHED_SLICE_NICE(nice)						\
2327d1a81b4SJeff Roberson     (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_SLICE_NTHRESH))
23335e6168fSJeff Roberson 
23435e6168fSJeff Roberson /*
235ed062c8dSJulian Elischer  * This macro determines whether or not the thread belongs on the current or
23635e6168fSJeff Roberson  * next run queue.
23735e6168fSJeff Roberson  */
23815dc847eSJeff Roberson #define	SCHED_INTERACTIVE(kg)						\
23915dc847eSJeff Roberson     (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
240a5f099d0SJeff Roberson #define	SCHED_CURR(kg, ke)						\
241f5c157d9SJohn Baldwin     ((ke->ke_thread->td_flags & TDF_BORROWING) || SCHED_INTERACTIVE(kg))
24235e6168fSJeff Roberson 
24335e6168fSJeff Roberson /*
24435e6168fSJeff Roberson  * Cpu percentage computation macros and defines.
24535e6168fSJeff Roberson  *
24635e6168fSJeff Roberson  * SCHED_CPU_TIME:	Number of seconds to average the cpu usage across.
24735e6168fSJeff Roberson  * SCHED_CPU_TICKS:	Number of hz ticks to average the cpu usage across.
24835e6168fSJeff Roberson  */
24935e6168fSJeff Roberson 
2505053d272SJeff Roberson #define	SCHED_CPU_TIME	10
25135e6168fSJeff Roberson #define	SCHED_CPU_TICKS	(hz * SCHED_CPU_TIME)
25235e6168fSJeff Roberson 
25335e6168fSJeff Roberson /*
25415dc847eSJeff Roberson  * kseq - per processor runqs and statistics.
25535e6168fSJeff Roberson  */
25635e6168fSJeff Roberson struct kseq {
257a8949de2SJeff Roberson 	struct runq	ksq_idle;		/* Queue of IDLE threads. */
25815dc847eSJeff Roberson 	struct runq	ksq_timeshare[2];	/* Run queues for !IDLE. */
25915dc847eSJeff Roberson 	struct runq	*ksq_next;		/* Next timeshare queue. */
26015dc847eSJeff Roberson 	struct runq	*ksq_curr;		/* Current queue. */
261ef1134c9SJeff Roberson 	int		ksq_load_timeshare;	/* Load for timeshare. */
26215dc847eSJeff Roberson 	int		ksq_load;		/* Aggregate load. */
263a0a931ceSJeff Roberson 	short		ksq_nice[SCHED_PRI_NRESV]; /* KSEs in each nice bin. */
26415dc847eSJeff Roberson 	short		ksq_nicemin;		/* Least nice. */
2655d7ef00cSJeff Roberson #ifdef SMP
26680f86c9fSJeff Roberson 	int			ksq_transferable;
26780f86c9fSJeff Roberson 	LIST_ENTRY(kseq)	ksq_siblings;	/* Next in kseq group. */
26880f86c9fSJeff Roberson 	struct kseq_group	*ksq_group;	/* Our processor group. */
269fa9c9717SJeff Roberson 	volatile struct kse	*ksq_assigned;	/* assigned by another CPU. */
27033916c36SJeff Roberson #else
27133916c36SJeff Roberson 	int		ksq_sysload;		/* For loadavg, !ITHD load. */
2725d7ef00cSJeff Roberson #endif
27335e6168fSJeff Roberson };
27435e6168fSJeff Roberson 
27580f86c9fSJeff Roberson #ifdef SMP
27680f86c9fSJeff Roberson /*
27780f86c9fSJeff Roberson  * kseq groups are groups of processors which can cheaply share threads.  When
27880f86c9fSJeff Roberson  * one processor in the group goes idle it will check the runqs of the other
27980f86c9fSJeff Roberson  * processors in its group prior to halting and waiting for an interrupt.
28080f86c9fSJeff Roberson  * These groups are suitable for SMT (Symetric Multi-Threading) and not NUMA.
28180f86c9fSJeff Roberson  * In a numa environment we'd want an idle bitmap per group and a two tiered
28280f86c9fSJeff Roberson  * load balancer.
28380f86c9fSJeff Roberson  */
28480f86c9fSJeff Roberson struct kseq_group {
28580f86c9fSJeff Roberson 	int	ksg_cpus;		/* Count of CPUs in this kseq group. */
286b2ae7ed7SMarcel Moolenaar 	cpumask_t ksg_cpumask;		/* Mask of cpus in this group. */
287b2ae7ed7SMarcel Moolenaar 	cpumask_t ksg_idlemask;		/* Idle cpus in this group. */
288b2ae7ed7SMarcel Moolenaar 	cpumask_t ksg_mask;		/* Bit mask for first cpu. */
289cac77d04SJeff Roberson 	int	ksg_load;		/* Total load of this group. */
29080f86c9fSJeff Roberson 	int	ksg_transferable;	/* Transferable load of this group. */
29180f86c9fSJeff Roberson 	LIST_HEAD(, kseq)	ksg_members; /* Linked list of all members. */
29280f86c9fSJeff Roberson };
29380f86c9fSJeff Roberson #endif
29480f86c9fSJeff Roberson 
29535e6168fSJeff Roberson /*
29635e6168fSJeff Roberson  * One kse queue per processor.
29735e6168fSJeff Roberson  */
2980a016a05SJeff Roberson #ifdef SMP
299b2ae7ed7SMarcel Moolenaar static cpumask_t kseq_idle;
300cac77d04SJeff Roberson static int ksg_maxid;
30122bf7d9aSJeff Roberson static struct kseq	kseq_cpu[MAXCPU];
30280f86c9fSJeff Roberson static struct kseq_group kseq_groups[MAXCPU];
303dc03363dSJeff Roberson static int bal_tick;
304dc03363dSJeff Roberson static int gbal_tick;
305598b368dSJeff Roberson static int balance_groups;
306dc03363dSJeff Roberson 
30780f86c9fSJeff Roberson #define	KSEQ_SELF()	(&kseq_cpu[PCPU_GET(cpuid)])
30880f86c9fSJeff Roberson #define	KSEQ_CPU(x)	(&kseq_cpu[(x)])
309cac77d04SJeff Roberson #define	KSEQ_ID(x)	((x) - kseq_cpu)
310cac77d04SJeff Roberson #define	KSEQ_GROUP(x)	(&kseq_groups[(x)])
31180f86c9fSJeff Roberson #else	/* !SMP */
31222bf7d9aSJeff Roberson static struct kseq	kseq_cpu;
313dc03363dSJeff Roberson 
3140a016a05SJeff Roberson #define	KSEQ_SELF()	(&kseq_cpu)
3150a016a05SJeff Roberson #define	KSEQ_CPU(x)	(&kseq_cpu)
3160a016a05SJeff Roberson #endif
31735e6168fSJeff Roberson 
318ed062c8dSJulian Elischer static void	slot_fill(struct ksegrp *kg);
319ed062c8dSJulian Elischer static struct kse *sched_choose(void);		/* XXX Should be thread * */
320245f3abfSJeff Roberson static void sched_slice(struct kse *ke);
32115dc847eSJeff Roberson static void sched_priority(struct ksegrp *kg);
322f5c157d9SJohn Baldwin static void sched_thread_priority(struct thread *td, u_char prio);
323e1f89c22SJeff Roberson static int sched_interact_score(struct ksegrp *kg);
3244b60e324SJeff Roberson static void sched_interact_update(struct ksegrp *kg);
325d322132cSJeff Roberson static void sched_interact_fork(struct ksegrp *kg);
32622bf7d9aSJeff Roberson static void sched_pctcpu_update(struct kse *ke);
32735e6168fSJeff Roberson 
3285d7ef00cSJeff Roberson /* Operations on per processor queues */
32922bf7d9aSJeff Roberson static struct kse * kseq_choose(struct kseq *kseq);
3300a016a05SJeff Roberson static void kseq_setup(struct kseq *kseq);
331155b9987SJeff Roberson static void kseq_load_add(struct kseq *kseq, struct kse *ke);
332155b9987SJeff Roberson static void kseq_load_rem(struct kseq *kseq, struct kse *ke);
333598b368dSJeff Roberson static __inline void kseq_runq_add(struct kseq *kseq, struct kse *ke, int);
334155b9987SJeff Roberson static __inline void kseq_runq_rem(struct kseq *kseq, struct kse *ke);
33515dc847eSJeff Roberson static void kseq_nice_add(struct kseq *kseq, int nice);
33615dc847eSJeff Roberson static void kseq_nice_rem(struct kseq *kseq, int nice);
3377cd650a9SJeff Roberson void kseq_print(int cpu);
3385d7ef00cSJeff Roberson #ifdef SMP
33980f86c9fSJeff Roberson static int kseq_transfer(struct kseq *ksq, struct kse *ke, int class);
34022bf7d9aSJeff Roberson static struct kse *runq_steal(struct runq *rq);
341dc03363dSJeff Roberson static void sched_balance(void);
342dc03363dSJeff Roberson static void sched_balance_groups(void);
343cac77d04SJeff Roberson static void sched_balance_group(struct kseq_group *ksg);
344cac77d04SJeff Roberson static void sched_balance_pair(struct kseq *high, struct kseq *low);
34522bf7d9aSJeff Roberson static void kseq_move(struct kseq *from, int cpu);
34680f86c9fSJeff Roberson static int kseq_idled(struct kseq *kseq);
34722bf7d9aSJeff Roberson static void kseq_notify(struct kse *ke, int cpu);
34822bf7d9aSJeff Roberson static void kseq_assign(struct kseq *);
34980f86c9fSJeff Roberson static struct kse *kseq_steal(struct kseq *kseq, int stealidle);
350598b368dSJeff Roberson #define	KSE_CAN_MIGRATE(ke)						\
3511e7fad6bSScott Long     ((ke)->ke_thread->td_pinned == 0 && ((ke)->ke_flags & KEF_BOUND) == 0)
3525d7ef00cSJeff Roberson #endif
3535d7ef00cSJeff Roberson 
35415dc847eSJeff Roberson void
3557cd650a9SJeff Roberson kseq_print(int cpu)
35615dc847eSJeff Roberson {
3577cd650a9SJeff Roberson 	struct kseq *kseq;
35815dc847eSJeff Roberson 	int i;
35915dc847eSJeff Roberson 
3607cd650a9SJeff Roberson 	kseq = KSEQ_CPU(cpu);
36115dc847eSJeff Roberson 
36215dc847eSJeff Roberson 	printf("kseq:\n");
36315dc847eSJeff Roberson 	printf("\tload:           %d\n", kseq->ksq_load);
364155b9987SJeff Roberson 	printf("\tload TIMESHARE: %d\n", kseq->ksq_load_timeshare);
365ef1134c9SJeff Roberson #ifdef SMP
36680f86c9fSJeff Roberson 	printf("\tload transferable: %d\n", kseq->ksq_transferable);
367ef1134c9SJeff Roberson #endif
36815dc847eSJeff Roberson 	printf("\tnicemin:\t%d\n", kseq->ksq_nicemin);
36915dc847eSJeff Roberson 	printf("\tnice counts:\n");
370a0a931ceSJeff Roberson 	for (i = 0; i < SCHED_PRI_NRESV; i++)
37115dc847eSJeff Roberson 		if (kseq->ksq_nice[i])
37215dc847eSJeff Roberson 			printf("\t\t%d = %d\n",
37315dc847eSJeff Roberson 			    i - SCHED_PRI_NHALF, kseq->ksq_nice[i]);
37415dc847eSJeff Roberson }
37515dc847eSJeff Roberson 
376155b9987SJeff Roberson static __inline void
377598b368dSJeff Roberson kseq_runq_add(struct kseq *kseq, struct kse *ke, int flags)
378155b9987SJeff Roberson {
379155b9987SJeff Roberson #ifdef SMP
380598b368dSJeff Roberson 	if (KSE_CAN_MIGRATE(ke)) {
38180f86c9fSJeff Roberson 		kseq->ksq_transferable++;
38280f86c9fSJeff Roberson 		kseq->ksq_group->ksg_transferable++;
3832454aaf5SJeff Roberson 		ke->ke_flags |= KEF_XFERABLE;
38480f86c9fSJeff Roberson 	}
385155b9987SJeff Roberson #endif
386598b368dSJeff Roberson 	runq_add(ke->ke_runq, ke, flags);
387155b9987SJeff Roberson }
388155b9987SJeff Roberson 
389155b9987SJeff Roberson static __inline void
390155b9987SJeff Roberson kseq_runq_rem(struct kseq *kseq, struct kse *ke)
391155b9987SJeff Roberson {
392155b9987SJeff Roberson #ifdef SMP
3932454aaf5SJeff Roberson 	if (ke->ke_flags & KEF_XFERABLE) {
39480f86c9fSJeff Roberson 		kseq->ksq_transferable--;
39580f86c9fSJeff Roberson 		kseq->ksq_group->ksg_transferable--;
3962454aaf5SJeff Roberson 		ke->ke_flags &= ~KEF_XFERABLE;
39780f86c9fSJeff Roberson 	}
398155b9987SJeff Roberson #endif
399155b9987SJeff Roberson 	runq_remove(ke->ke_runq, ke);
400155b9987SJeff Roberson }
401155b9987SJeff Roberson 
402a8949de2SJeff Roberson static void
403155b9987SJeff Roberson kseq_load_add(struct kseq *kseq, struct kse *ke)
4045d7ef00cSJeff Roberson {
405ef1134c9SJeff Roberson 	int class;
406b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
407ef1134c9SJeff Roberson 	class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
408ef1134c9SJeff Roberson 	if (class == PRI_TIMESHARE)
409ef1134c9SJeff Roberson 		kseq->ksq_load_timeshare++;
41015dc847eSJeff Roberson 	kseq->ksq_load++;
41181d47d3fSJeff Roberson 	CTR1(KTR_SCHED, "load: %d", kseq->ksq_load);
412207a6c0dSDavid E. O'Brien 	if (class != PRI_ITHD && (ke->ke_proc->p_flag & P_NOLOAD) == 0)
41333916c36SJeff Roberson #ifdef SMP
414cac77d04SJeff Roberson 		kseq->ksq_group->ksg_load++;
41533916c36SJeff Roberson #else
41633916c36SJeff Roberson 		kseq->ksq_sysload++;
417cac77d04SJeff Roberson #endif
41815dc847eSJeff Roberson 	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
419fa885116SJulian Elischer 		kseq_nice_add(kseq, ke->ke_proc->p_nice);
4205d7ef00cSJeff Roberson }
42115dc847eSJeff Roberson 
422a8949de2SJeff Roberson static void
423155b9987SJeff Roberson kseq_load_rem(struct kseq *kseq, struct kse *ke)
4245d7ef00cSJeff Roberson {
425ef1134c9SJeff Roberson 	int class;
426b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
427ef1134c9SJeff Roberson 	class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
428ef1134c9SJeff Roberson 	if (class == PRI_TIMESHARE)
429ef1134c9SJeff Roberson 		kseq->ksq_load_timeshare--;
430207a6c0dSDavid E. O'Brien 	if (class != PRI_ITHD  && (ke->ke_proc->p_flag & P_NOLOAD) == 0)
43133916c36SJeff Roberson #ifdef SMP
432cac77d04SJeff Roberson 		kseq->ksq_group->ksg_load--;
43333916c36SJeff Roberson #else
43433916c36SJeff Roberson 		kseq->ksq_sysload--;
435cac77d04SJeff Roberson #endif
43615dc847eSJeff Roberson 	kseq->ksq_load--;
43781d47d3fSJeff Roberson 	CTR1(KTR_SCHED, "load: %d", kseq->ksq_load);
43815dc847eSJeff Roberson 	ke->ke_runq = NULL;
43915dc847eSJeff Roberson 	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
440fa885116SJulian Elischer 		kseq_nice_rem(kseq, ke->ke_proc->p_nice);
4415d7ef00cSJeff Roberson }
4425d7ef00cSJeff Roberson 
44315dc847eSJeff Roberson static void
44415dc847eSJeff Roberson kseq_nice_add(struct kseq *kseq, int nice)
44515dc847eSJeff Roberson {
446b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
44715dc847eSJeff Roberson 	/* Normalize to zero. */
44815dc847eSJeff Roberson 	kseq->ksq_nice[nice + SCHED_PRI_NHALF]++;
449ef1134c9SJeff Roberson 	if (nice < kseq->ksq_nicemin || kseq->ksq_load_timeshare == 1)
45015dc847eSJeff Roberson 		kseq->ksq_nicemin = nice;
45115dc847eSJeff Roberson }
45215dc847eSJeff Roberson 
45315dc847eSJeff Roberson static void
45415dc847eSJeff Roberson kseq_nice_rem(struct kseq *kseq, int nice)
45515dc847eSJeff Roberson {
45615dc847eSJeff Roberson 	int n;
45715dc847eSJeff Roberson 
458b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
45915dc847eSJeff Roberson 	/* Normalize to zero. */
46015dc847eSJeff Roberson 	n = nice + SCHED_PRI_NHALF;
46115dc847eSJeff Roberson 	kseq->ksq_nice[n]--;
46215dc847eSJeff Roberson 	KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count."));
46315dc847eSJeff Roberson 
46415dc847eSJeff Roberson 	/*
46515dc847eSJeff Roberson 	 * If this wasn't the smallest nice value or there are more in
46615dc847eSJeff Roberson 	 * this bucket we can just return.  Otherwise we have to recalculate
46715dc847eSJeff Roberson 	 * the smallest nice.
46815dc847eSJeff Roberson 	 */
46915dc847eSJeff Roberson 	if (nice != kseq->ksq_nicemin ||
47015dc847eSJeff Roberson 	    kseq->ksq_nice[n] != 0 ||
471ef1134c9SJeff Roberson 	    kseq->ksq_load_timeshare == 0)
47215dc847eSJeff Roberson 		return;
47315dc847eSJeff Roberson 
474a0a931ceSJeff Roberson 	for (; n < SCHED_PRI_NRESV; n++)
47515dc847eSJeff Roberson 		if (kseq->ksq_nice[n]) {
47615dc847eSJeff Roberson 			kseq->ksq_nicemin = n - SCHED_PRI_NHALF;
47715dc847eSJeff Roberson 			return;
47815dc847eSJeff Roberson 		}
47915dc847eSJeff Roberson }
48015dc847eSJeff Roberson 
4815d7ef00cSJeff Roberson #ifdef SMP
482356500a3SJeff Roberson /*
483155b9987SJeff Roberson  * sched_balance is a simple CPU load balancing algorithm.  It operates by
484356500a3SJeff Roberson  * finding the least loaded and most loaded cpu and equalizing their load
485356500a3SJeff Roberson  * by migrating some processes.
486356500a3SJeff Roberson  *
487356500a3SJeff Roberson  * Dealing only with two CPUs at a time has two advantages.  Firstly, most
488356500a3SJeff Roberson  * installations will only have 2 cpus.  Secondly, load balancing too much at
489356500a3SJeff Roberson  * once can have an unpleasant effect on the system.  The scheduler rarely has
490356500a3SJeff Roberson  * enough information to make perfect decisions.  So this algorithm chooses
491356500a3SJeff Roberson  * algorithm simplicity and more gradual effects on load in larger systems.
492356500a3SJeff Roberson  *
493356500a3SJeff Roberson  * It could be improved by considering the priorities and slices assigned to
494356500a3SJeff Roberson  * each task prior to balancing them.  There are many pathological cases with
495356500a3SJeff Roberson  * any approach and so the semi random algorithm below may work as well as any.
496356500a3SJeff Roberson  *
497356500a3SJeff Roberson  */
49822bf7d9aSJeff Roberson static void
499dc03363dSJeff Roberson sched_balance(void)
500356500a3SJeff Roberson {
501cac77d04SJeff Roberson 	struct kseq_group *high;
502cac77d04SJeff Roberson 	struct kseq_group *low;
503cac77d04SJeff Roberson 	struct kseq_group *ksg;
504cac77d04SJeff Roberson 	int cnt;
505356500a3SJeff Roberson 	int i;
506356500a3SJeff Roberson 
507598b368dSJeff Roberson 	bal_tick = ticks + (random() % (hz * 2));
50886f8ae96SJeff Roberson 	if (smp_started == 0)
509598b368dSJeff Roberson 		return;
510cac77d04SJeff Roberson 	low = high = NULL;
511cac77d04SJeff Roberson 	i = random() % (ksg_maxid + 1);
512cac77d04SJeff Roberson 	for (cnt = 0; cnt <= ksg_maxid; cnt++) {
513cac77d04SJeff Roberson 		ksg = KSEQ_GROUP(i);
514cac77d04SJeff Roberson 		/*
515cac77d04SJeff Roberson 		 * Find the CPU with the highest load that has some
516cac77d04SJeff Roberson 		 * threads to transfer.
517cac77d04SJeff Roberson 		 */
518cac77d04SJeff Roberson 		if ((high == NULL || ksg->ksg_load > high->ksg_load)
519cac77d04SJeff Roberson 		    && ksg->ksg_transferable)
520cac77d04SJeff Roberson 			high = ksg;
521cac77d04SJeff Roberson 		if (low == NULL || ksg->ksg_load < low->ksg_load)
522cac77d04SJeff Roberson 			low = ksg;
523cac77d04SJeff Roberson 		if (++i > ksg_maxid)
524cac77d04SJeff Roberson 			i = 0;
525cac77d04SJeff Roberson 	}
526cac77d04SJeff Roberson 	if (low != NULL && high != NULL && high != low)
527cac77d04SJeff Roberson 		sched_balance_pair(LIST_FIRST(&high->ksg_members),
528cac77d04SJeff Roberson 		    LIST_FIRST(&low->ksg_members));
529cac77d04SJeff Roberson }
53086f8ae96SJeff Roberson 
531cac77d04SJeff Roberson static void
532dc03363dSJeff Roberson sched_balance_groups(void)
533cac77d04SJeff Roberson {
534cac77d04SJeff Roberson 	int i;
535cac77d04SJeff Roberson 
536598b368dSJeff Roberson 	gbal_tick = ticks + (random() % (hz * 2));
537dc03363dSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
538cac77d04SJeff Roberson 	if (smp_started)
539cac77d04SJeff Roberson 		for (i = 0; i <= ksg_maxid; i++)
540cac77d04SJeff Roberson 			sched_balance_group(KSEQ_GROUP(i));
541356500a3SJeff Roberson }
542cac77d04SJeff Roberson 
543cac77d04SJeff Roberson static void
544cac77d04SJeff Roberson sched_balance_group(struct kseq_group *ksg)
545cac77d04SJeff Roberson {
546cac77d04SJeff Roberson 	struct kseq *kseq;
547cac77d04SJeff Roberson 	struct kseq *high;
548cac77d04SJeff Roberson 	struct kseq *low;
549cac77d04SJeff Roberson 	int load;
550cac77d04SJeff Roberson 
551cac77d04SJeff Roberson 	if (ksg->ksg_transferable == 0)
552cac77d04SJeff Roberson 		return;
553cac77d04SJeff Roberson 	low = NULL;
554cac77d04SJeff Roberson 	high = NULL;
555cac77d04SJeff Roberson 	LIST_FOREACH(kseq, &ksg->ksg_members, ksq_siblings) {
556cac77d04SJeff Roberson 		load = kseq->ksq_load;
557cac77d04SJeff Roberson 		if (high == NULL || load > high->ksq_load)
558cac77d04SJeff Roberson 			high = kseq;
559cac77d04SJeff Roberson 		if (low == NULL || load < low->ksq_load)
560cac77d04SJeff Roberson 			low = kseq;
561356500a3SJeff Roberson 	}
562cac77d04SJeff Roberson 	if (high != NULL && low != NULL && high != low)
563cac77d04SJeff Roberson 		sched_balance_pair(high, low);
564356500a3SJeff Roberson }
565cac77d04SJeff Roberson 
566cac77d04SJeff Roberson static void
567cac77d04SJeff Roberson sched_balance_pair(struct kseq *high, struct kseq *low)
568cac77d04SJeff Roberson {
569cac77d04SJeff Roberson 	int transferable;
570cac77d04SJeff Roberson 	int high_load;
571cac77d04SJeff Roberson 	int low_load;
572cac77d04SJeff Roberson 	int move;
573cac77d04SJeff Roberson 	int diff;
574cac77d04SJeff Roberson 	int i;
575cac77d04SJeff Roberson 
57680f86c9fSJeff Roberson 	/*
57780f86c9fSJeff Roberson 	 * If we're transfering within a group we have to use this specific
57880f86c9fSJeff Roberson 	 * kseq's transferable count, otherwise we can steal from other members
57980f86c9fSJeff Roberson 	 * of the group.
58080f86c9fSJeff Roberson 	 */
581cac77d04SJeff Roberson 	if (high->ksq_group == low->ksq_group) {
582cac77d04SJeff Roberson 		transferable = high->ksq_transferable;
583cac77d04SJeff Roberson 		high_load = high->ksq_load;
584cac77d04SJeff Roberson 		low_load = low->ksq_load;
585cac77d04SJeff Roberson 	} else {
586cac77d04SJeff Roberson 		transferable = high->ksq_group->ksg_transferable;
587cac77d04SJeff Roberson 		high_load = high->ksq_group->ksg_load;
588cac77d04SJeff Roberson 		low_load = low->ksq_group->ksg_load;
589cac77d04SJeff Roberson 	}
59080f86c9fSJeff Roberson 	if (transferable == 0)
591cac77d04SJeff Roberson 		return;
592155b9987SJeff Roberson 	/*
593155b9987SJeff Roberson 	 * Determine what the imbalance is and then adjust that to how many
59480f86c9fSJeff Roberson 	 * kses we actually have to give up (transferable).
595155b9987SJeff Roberson 	 */
596cac77d04SJeff Roberson 	diff = high_load - low_load;
597356500a3SJeff Roberson 	move = diff / 2;
598356500a3SJeff Roberson 	if (diff & 0x1)
599356500a3SJeff Roberson 		move++;
60080f86c9fSJeff Roberson 	move = min(move, transferable);
601356500a3SJeff Roberson 	for (i = 0; i < move; i++)
602cac77d04SJeff Roberson 		kseq_move(high, KSEQ_ID(low));
603356500a3SJeff Roberson 	return;
604356500a3SJeff Roberson }
605356500a3SJeff Roberson 
60622bf7d9aSJeff Roberson static void
607356500a3SJeff Roberson kseq_move(struct kseq *from, int cpu)
608356500a3SJeff Roberson {
60980f86c9fSJeff Roberson 	struct kseq *kseq;
61080f86c9fSJeff Roberson 	struct kseq *to;
611356500a3SJeff Roberson 	struct kse *ke;
612356500a3SJeff Roberson 
61380f86c9fSJeff Roberson 	kseq = from;
61480f86c9fSJeff Roberson 	to = KSEQ_CPU(cpu);
61580f86c9fSJeff Roberson 	ke = kseq_steal(kseq, 1);
61680f86c9fSJeff Roberson 	if (ke == NULL) {
61780f86c9fSJeff Roberson 		struct kseq_group *ksg;
61880f86c9fSJeff Roberson 
61980f86c9fSJeff Roberson 		ksg = kseq->ksq_group;
62080f86c9fSJeff Roberson 		LIST_FOREACH(kseq, &ksg->ksg_members, ksq_siblings) {
62180f86c9fSJeff Roberson 			if (kseq == from || kseq->ksq_transferable == 0)
62280f86c9fSJeff Roberson 				continue;
62380f86c9fSJeff Roberson 			ke = kseq_steal(kseq, 1);
62480f86c9fSJeff Roberson 			break;
62580f86c9fSJeff Roberson 		}
62680f86c9fSJeff Roberson 		if (ke == NULL)
62780f86c9fSJeff Roberson 			panic("kseq_move: No KSEs available with a "
62880f86c9fSJeff Roberson 			    "transferable count of %d\n",
62980f86c9fSJeff Roberson 			    ksg->ksg_transferable);
63080f86c9fSJeff Roberson 	}
63180f86c9fSJeff Roberson 	if (kseq == to)
63280f86c9fSJeff Roberson 		return;
633356500a3SJeff Roberson 	ke->ke_state = KES_THREAD;
63480f86c9fSJeff Roberson 	kseq_runq_rem(kseq, ke);
63580f86c9fSJeff Roberson 	kseq_load_rem(kseq, ke);
636112b6d3aSJeff Roberson 	kseq_notify(ke, cpu);
637356500a3SJeff Roberson }
63822bf7d9aSJeff Roberson 
63980f86c9fSJeff Roberson static int
64080f86c9fSJeff Roberson kseq_idled(struct kseq *kseq)
64122bf7d9aSJeff Roberson {
64280f86c9fSJeff Roberson 	struct kseq_group *ksg;
64380f86c9fSJeff Roberson 	struct kseq *steal;
64480f86c9fSJeff Roberson 	struct kse *ke;
64580f86c9fSJeff Roberson 
64680f86c9fSJeff Roberson 	ksg = kseq->ksq_group;
64780f86c9fSJeff Roberson 	/*
64880f86c9fSJeff Roberson 	 * If we're in a cpu group, try and steal kses from another cpu in
64980f86c9fSJeff Roberson 	 * the group before idling.
65080f86c9fSJeff Roberson 	 */
65180f86c9fSJeff Roberson 	if (ksg->ksg_cpus > 1 && ksg->ksg_transferable) {
65280f86c9fSJeff Roberson 		LIST_FOREACH(steal, &ksg->ksg_members, ksq_siblings) {
65380f86c9fSJeff Roberson 			if (steal == kseq || steal->ksq_transferable == 0)
65480f86c9fSJeff Roberson 				continue;
65580f86c9fSJeff Roberson 			ke = kseq_steal(steal, 0);
65680f86c9fSJeff Roberson 			if (ke == NULL)
65780f86c9fSJeff Roberson 				continue;
65880f86c9fSJeff Roberson 			ke->ke_state = KES_THREAD;
65980f86c9fSJeff Roberson 			kseq_runq_rem(steal, ke);
66080f86c9fSJeff Roberson 			kseq_load_rem(steal, ke);
66180f86c9fSJeff Roberson 			ke->ke_cpu = PCPU_GET(cpuid);
662598b368dSJeff Roberson 			ke->ke_flags |= KEF_INTERNAL | KEF_HOLD;
663598b368dSJeff Roberson 			sched_add(ke->ke_thread, SRQ_YIELDING);
66480f86c9fSJeff Roberson 			return (0);
66580f86c9fSJeff Roberson 		}
66680f86c9fSJeff Roberson 	}
66780f86c9fSJeff Roberson 	/*
66880f86c9fSJeff Roberson 	 * We only set the idled bit when all of the cpus in the group are
66980f86c9fSJeff Roberson 	 * idle.  Otherwise we could get into a situation where a KSE bounces
67080f86c9fSJeff Roberson 	 * back and forth between two idle cores on seperate physical CPUs.
67180f86c9fSJeff Roberson 	 */
67280f86c9fSJeff Roberson 	ksg->ksg_idlemask |= PCPU_GET(cpumask);
67380f86c9fSJeff Roberson 	if (ksg->ksg_idlemask != ksg->ksg_cpumask)
67480f86c9fSJeff Roberson 		return (1);
67580f86c9fSJeff Roberson 	atomic_set_int(&kseq_idle, ksg->ksg_mask);
67680f86c9fSJeff Roberson 	return (1);
67722bf7d9aSJeff Roberson }
67822bf7d9aSJeff Roberson 
67922bf7d9aSJeff Roberson static void
68022bf7d9aSJeff Roberson kseq_assign(struct kseq *kseq)
68122bf7d9aSJeff Roberson {
68222bf7d9aSJeff Roberson 	struct kse *nke;
68322bf7d9aSJeff Roberson 	struct kse *ke;
68422bf7d9aSJeff Roberson 
68522bf7d9aSJeff Roberson 	do {
68600fbcda8SAlexander Kabaev 		*(volatile struct kse **)&ke = kseq->ksq_assigned;
68722bf7d9aSJeff Roberson 	} while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke, NULL));
68822bf7d9aSJeff Roberson 	for (; ke != NULL; ke = nke) {
68922bf7d9aSJeff Roberson 		nke = ke->ke_assign;
690598b368dSJeff Roberson 		kseq->ksq_group->ksg_load--;
691598b368dSJeff Roberson 		kseq->ksq_load--;
69222bf7d9aSJeff Roberson 		ke->ke_flags &= ~KEF_ASSIGNED;
693598b368dSJeff Roberson 		ke->ke_flags |= KEF_INTERNAL | KEF_HOLD;
694598b368dSJeff Roberson 		sched_add(ke->ke_thread, SRQ_YIELDING);
69522bf7d9aSJeff Roberson 	}
69622bf7d9aSJeff Roberson }
69722bf7d9aSJeff Roberson 
69822bf7d9aSJeff Roberson static void
69922bf7d9aSJeff Roberson kseq_notify(struct kse *ke, int cpu)
70022bf7d9aSJeff Roberson {
70122bf7d9aSJeff Roberson 	struct kseq *kseq;
70222bf7d9aSJeff Roberson 	struct thread *td;
70322bf7d9aSJeff Roberson 	struct pcpu *pcpu;
704598b368dSJeff Roberson 	int class;
7052454aaf5SJeff Roberson 	int prio;
70622bf7d9aSJeff Roberson 
707598b368dSJeff Roberson 	kseq = KSEQ_CPU(cpu);
708598b368dSJeff Roberson 	/* XXX */
709598b368dSJeff Roberson 	class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
710598b368dSJeff Roberson 	if ((class == PRI_TIMESHARE || class == PRI_REALTIME) &&
711598b368dSJeff Roberson 	    (kseq_idle & kseq->ksq_group->ksg_mask))
712598b368dSJeff Roberson 		atomic_clear_int(&kseq_idle, kseq->ksq_group->ksg_mask);
713598b368dSJeff Roberson 	kseq->ksq_group->ksg_load++;
714598b368dSJeff Roberson 	kseq->ksq_load++;
71586e1c22aSJeff Roberson 	ke->ke_cpu = cpu;
71622bf7d9aSJeff Roberson 	ke->ke_flags |= KEF_ASSIGNED;
7172454aaf5SJeff Roberson 	prio = ke->ke_thread->td_priority;
71822bf7d9aSJeff Roberson 
7190c0a98b2SJeff Roberson 	/*
72022bf7d9aSJeff Roberson 	 * Place a KSE on another cpu's queue and force a resched.
72122bf7d9aSJeff Roberson 	 */
72222bf7d9aSJeff Roberson 	do {
72300fbcda8SAlexander Kabaev 		*(volatile struct kse **)&ke->ke_assign = kseq->ksq_assigned;
72422bf7d9aSJeff Roberson 	} while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke->ke_assign, ke));
7252454aaf5SJeff Roberson 	/*
7262454aaf5SJeff Roberson 	 * Without sched_lock we could lose a race where we set NEEDRESCHED
7272454aaf5SJeff Roberson 	 * on a thread that is switched out before the IPI is delivered.  This
7282454aaf5SJeff Roberson 	 * would lead us to miss the resched.  This will be a problem once
7292454aaf5SJeff Roberson 	 * sched_lock is pushed down.
7302454aaf5SJeff Roberson 	 */
73122bf7d9aSJeff Roberson 	pcpu = pcpu_find(cpu);
73222bf7d9aSJeff Roberson 	td = pcpu->pc_curthread;
73322bf7d9aSJeff Roberson 	if (ke->ke_thread->td_priority < td->td_priority ||
73422bf7d9aSJeff Roberson 	    td == pcpu->pc_idlethread) {
73522bf7d9aSJeff Roberson 		td->td_flags |= TDF_NEEDRESCHED;
73622bf7d9aSJeff Roberson 		ipi_selected(1 << cpu, IPI_AST);
73722bf7d9aSJeff Roberson 	}
73822bf7d9aSJeff Roberson }
73922bf7d9aSJeff Roberson 
74022bf7d9aSJeff Roberson static struct kse *
74122bf7d9aSJeff Roberson runq_steal(struct runq *rq)
74222bf7d9aSJeff Roberson {
74322bf7d9aSJeff Roberson 	struct rqhead *rqh;
74422bf7d9aSJeff Roberson 	struct rqbits *rqb;
74522bf7d9aSJeff Roberson 	struct kse *ke;
74622bf7d9aSJeff Roberson 	int word;
74722bf7d9aSJeff Roberson 	int bit;
74822bf7d9aSJeff Roberson 
74922bf7d9aSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
75022bf7d9aSJeff Roberson 	rqb = &rq->rq_status;
75122bf7d9aSJeff Roberson 	for (word = 0; word < RQB_LEN; word++) {
75222bf7d9aSJeff Roberson 		if (rqb->rqb_bits[word] == 0)
75322bf7d9aSJeff Roberson 			continue;
75422bf7d9aSJeff Roberson 		for (bit = 0; bit < RQB_BPW; bit++) {
755a2640c9bSPeter Wemm 			if ((rqb->rqb_bits[word] & (1ul << bit)) == 0)
75622bf7d9aSJeff Roberson 				continue;
75722bf7d9aSJeff Roberson 			rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
75822bf7d9aSJeff Roberson 			TAILQ_FOREACH(ke, rqh, ke_procq) {
759598b368dSJeff Roberson 				if (KSE_CAN_MIGRATE(ke))
76022bf7d9aSJeff Roberson 					return (ke);
76122bf7d9aSJeff Roberson 			}
76222bf7d9aSJeff Roberson 		}
76322bf7d9aSJeff Roberson 	}
76422bf7d9aSJeff Roberson 	return (NULL);
76522bf7d9aSJeff Roberson }
76622bf7d9aSJeff Roberson 
76722bf7d9aSJeff Roberson static struct kse *
76880f86c9fSJeff Roberson kseq_steal(struct kseq *kseq, int stealidle)
76922bf7d9aSJeff Roberson {
77022bf7d9aSJeff Roberson 	struct kse *ke;
77122bf7d9aSJeff Roberson 
77280f86c9fSJeff Roberson 	/*
77380f86c9fSJeff Roberson 	 * Steal from next first to try to get a non-interactive task that
77480f86c9fSJeff Roberson 	 * may not have run for a while.
77580f86c9fSJeff Roberson 	 */
77622bf7d9aSJeff Roberson 	if ((ke = runq_steal(kseq->ksq_next)) != NULL)
77722bf7d9aSJeff Roberson 		return (ke);
77880f86c9fSJeff Roberson 	if ((ke = runq_steal(kseq->ksq_curr)) != NULL)
77980f86c9fSJeff Roberson 		return (ke);
78080f86c9fSJeff Roberson 	if (stealidle)
78122bf7d9aSJeff Roberson 		return (runq_steal(&kseq->ksq_idle));
78280f86c9fSJeff Roberson 	return (NULL);
78322bf7d9aSJeff Roberson }
78480f86c9fSJeff Roberson 
78580f86c9fSJeff Roberson int
78680f86c9fSJeff Roberson kseq_transfer(struct kseq *kseq, struct kse *ke, int class)
78780f86c9fSJeff Roberson {
788598b368dSJeff Roberson 	struct kseq_group *nksg;
78980f86c9fSJeff Roberson 	struct kseq_group *ksg;
790598b368dSJeff Roberson 	struct kseq *old;
79180f86c9fSJeff Roberson 	int cpu;
792598b368dSJeff Roberson 	int idx;
79380f86c9fSJeff Roberson 
794670c524fSJeff Roberson 	if (smp_started == 0)
795670c524fSJeff Roberson 		return (0);
79680f86c9fSJeff Roberson 	cpu = 0;
79780f86c9fSJeff Roberson 	/*
7982454aaf5SJeff Roberson 	 * If our load exceeds a certain threshold we should attempt to
7992454aaf5SJeff Roberson 	 * reassign this thread.  The first candidate is the cpu that
8002454aaf5SJeff Roberson 	 * originally ran the thread.  If it is idle, assign it there,
8012454aaf5SJeff Roberson 	 * otherwise, pick an idle cpu.
8022454aaf5SJeff Roberson 	 *
8032454aaf5SJeff Roberson 	 * The threshold at which we start to reassign kses has a large impact
804670c524fSJeff Roberson 	 * on the overall performance of the system.  Tuned too high and
805670c524fSJeff Roberson 	 * some CPUs may idle.  Too low and there will be excess migration
806d50c87deSOlivier Houchard 	 * and context switches.
807670c524fSJeff Roberson 	 */
808598b368dSJeff Roberson 	old = KSEQ_CPU(ke->ke_cpu);
809598b368dSJeff Roberson 	nksg = old->ksq_group;
8102454aaf5SJeff Roberson 	ksg = kseq->ksq_group;
811598b368dSJeff Roberson 	if (kseq_idle) {
812598b368dSJeff Roberson 		if (kseq_idle & nksg->ksg_mask) {
813598b368dSJeff Roberson 			cpu = ffs(nksg->ksg_idlemask);
814598b368dSJeff Roberson 			if (cpu) {
815598b368dSJeff Roberson 				CTR2(KTR_SCHED,
816598b368dSJeff Roberson 				    "kseq_transfer: %p found old cpu %X "
817598b368dSJeff Roberson 				    "in idlemask.", ke, cpu);
8182454aaf5SJeff Roberson 				goto migrate;
8192454aaf5SJeff Roberson 			}
820598b368dSJeff Roberson 		}
82180f86c9fSJeff Roberson 		/*
82280f86c9fSJeff Roberson 		 * Multiple cpus could find this bit simultaneously
82380f86c9fSJeff Roberson 		 * but the race shouldn't be terrible.
82480f86c9fSJeff Roberson 		 */
82580f86c9fSJeff Roberson 		cpu = ffs(kseq_idle);
826598b368dSJeff Roberson 		if (cpu) {
827598b368dSJeff Roberson 			CTR2(KTR_SCHED, "kseq_transfer: %p found %X "
828598b368dSJeff Roberson 			    "in idlemask.", ke, cpu);
8292454aaf5SJeff Roberson 			goto migrate;
83080f86c9fSJeff Roberson 		}
831598b368dSJeff Roberson 	}
832598b368dSJeff Roberson 	idx = 0;
833598b368dSJeff Roberson #if 0
834598b368dSJeff Roberson 	if (old->ksq_load < kseq->ksq_load) {
835598b368dSJeff Roberson 		cpu = ke->ke_cpu + 1;
836598b368dSJeff Roberson 		CTR2(KTR_SCHED, "kseq_transfer: %p old cpu %X "
837598b368dSJeff Roberson 		    "load less than ours.", ke, cpu);
838598b368dSJeff Roberson 		goto migrate;
839598b368dSJeff Roberson 	}
840598b368dSJeff Roberson 	/*
841598b368dSJeff Roberson 	 * No new CPU was found, look for one with less load.
842598b368dSJeff Roberson 	 */
843598b368dSJeff Roberson 	for (idx = 0; idx <= ksg_maxid; idx++) {
844598b368dSJeff Roberson 		nksg = KSEQ_GROUP(idx);
845598b368dSJeff Roberson 		if (nksg->ksg_load /*+ (nksg->ksg_cpus  * 2)*/ < ksg->ksg_load) {
846598b368dSJeff Roberson 			cpu = ffs(nksg->ksg_cpumask);
847598b368dSJeff Roberson 			CTR2(KTR_SCHED, "kseq_transfer: %p cpu %X load less "
848598b368dSJeff Roberson 			    "than ours.", ke, cpu);
849598b368dSJeff Roberson 			goto migrate;
850598b368dSJeff Roberson 		}
851598b368dSJeff Roberson 	}
852598b368dSJeff Roberson #endif
85380f86c9fSJeff Roberson 	/*
85480f86c9fSJeff Roberson 	 * If another cpu in this group has idled, assign a thread over
85580f86c9fSJeff Roberson 	 * to them after checking to see if there are idled groups.
85680f86c9fSJeff Roberson 	 */
8572454aaf5SJeff Roberson 	if (ksg->ksg_idlemask) {
85880f86c9fSJeff Roberson 		cpu = ffs(ksg->ksg_idlemask);
859598b368dSJeff Roberson 		if (cpu) {
860598b368dSJeff Roberson 			CTR2(KTR_SCHED, "kseq_transfer: %p cpu %X idle in "
861598b368dSJeff Roberson 			    "group.", ke, cpu);
8622454aaf5SJeff Roberson 			goto migrate;
86380f86c9fSJeff Roberson 		}
864598b368dSJeff Roberson 	}
8652454aaf5SJeff Roberson 	return (0);
8662454aaf5SJeff Roberson migrate:
8672454aaf5SJeff Roberson 	/*
86880f86c9fSJeff Roberson 	 * Now that we've found an idle CPU, migrate the thread.
86980f86c9fSJeff Roberson 	 */
87080f86c9fSJeff Roberson 	cpu--;
87180f86c9fSJeff Roberson 	ke->ke_runq = NULL;
87280f86c9fSJeff Roberson 	kseq_notify(ke, cpu);
8732454aaf5SJeff Roberson 
87480f86c9fSJeff Roberson 	return (1);
87580f86c9fSJeff Roberson }
87680f86c9fSJeff Roberson 
87722bf7d9aSJeff Roberson #endif	/* SMP */
87822bf7d9aSJeff Roberson 
87922bf7d9aSJeff Roberson /*
88022bf7d9aSJeff Roberson  * Pick the highest priority task we have and return it.
8810c0a98b2SJeff Roberson  */
8820c0a98b2SJeff Roberson 
88322bf7d9aSJeff Roberson static struct kse *
88422bf7d9aSJeff Roberson kseq_choose(struct kseq *kseq)
8855d7ef00cSJeff Roberson {
8865d7ef00cSJeff Roberson 	struct runq *swap;
8870516c8ddSJeff Roberson 	struct kse *ke;
8880516c8ddSJeff Roberson 	int nice;
8895d7ef00cSJeff Roberson 
890b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
89115dc847eSJeff Roberson 	swap = NULL;
892a8949de2SJeff Roberson 
89315dc847eSJeff Roberson 	for (;;) {
89415dc847eSJeff Roberson 		ke = runq_choose(kseq->ksq_curr);
89515dc847eSJeff Roberson 		if (ke == NULL) {
89615dc847eSJeff Roberson 			/*
897bf0acc27SJohn Baldwin 			 * We already swapped once and didn't get anywhere.
89815dc847eSJeff Roberson 			 */
89915dc847eSJeff Roberson 			if (swap)
90015dc847eSJeff Roberson 				break;
9015d7ef00cSJeff Roberson 			swap = kseq->ksq_curr;
9025d7ef00cSJeff Roberson 			kseq->ksq_curr = kseq->ksq_next;
9035d7ef00cSJeff Roberson 			kseq->ksq_next = swap;
90415dc847eSJeff Roberson 			continue;
905a8949de2SJeff Roberson 		}
90615dc847eSJeff Roberson 		/*
90715dc847eSJeff Roberson 		 * If we encounter a slice of 0 the kse is in a
90815dc847eSJeff Roberson 		 * TIMESHARE kse group and its nice was too far out
90915dc847eSJeff Roberson 		 * of the range that receives slices.
91015dc847eSJeff Roberson 		 */
9110516c8ddSJeff Roberson 		nice = ke->ke_proc->p_nice + (0 - kseq->ksq_nicemin);
9128ffb8f55SJeff Roberson 		if (ke->ke_slice == 0 || (nice > SCHED_SLICE_NTHRESH &&
9138ffb8f55SJeff Roberson 		    ke->ke_proc->p_nice != 0)) {
91415dc847eSJeff Roberson 			runq_remove(ke->ke_runq, ke);
91515dc847eSJeff Roberson 			sched_slice(ke);
91615dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_next;
917c20c691bSJulian Elischer 			runq_add(ke->ke_runq, ke, 0);
91815dc847eSJeff Roberson 			continue;
91915dc847eSJeff Roberson 		}
92015dc847eSJeff Roberson 		return (ke);
92115dc847eSJeff Roberson 	}
92215dc847eSJeff Roberson 
923a8949de2SJeff Roberson 	return (runq_choose(&kseq->ksq_idle));
924245f3abfSJeff Roberson }
9250a016a05SJeff Roberson 
9260a016a05SJeff Roberson static void
9270a016a05SJeff Roberson kseq_setup(struct kseq *kseq)
9280a016a05SJeff Roberson {
92915dc847eSJeff Roberson 	runq_init(&kseq->ksq_timeshare[0]);
93015dc847eSJeff Roberson 	runq_init(&kseq->ksq_timeshare[1]);
931a8949de2SJeff Roberson 	runq_init(&kseq->ksq_idle);
93215dc847eSJeff Roberson 	kseq->ksq_curr = &kseq->ksq_timeshare[0];
93315dc847eSJeff Roberson 	kseq->ksq_next = &kseq->ksq_timeshare[1];
9347cd650a9SJeff Roberson 	kseq->ksq_load = 0;
935ef1134c9SJeff Roberson 	kseq->ksq_load_timeshare = 0;
9360a016a05SJeff Roberson }
9370a016a05SJeff Roberson 
93835e6168fSJeff Roberson static void
93935e6168fSJeff Roberson sched_setup(void *dummy)
94035e6168fSJeff Roberson {
9410ec896fdSJeff Roberson #ifdef SMP
94235e6168fSJeff Roberson 	int i;
9430ec896fdSJeff Roberson #endif
94435e6168fSJeff Roberson 
945e493a5d9SJeff Roberson 	slice_min = (hz/100);	/* 10ms */
946e493a5d9SJeff Roberson 	slice_max = (hz/7);	/* ~140ms */
947e1f89c22SJeff Roberson 
948356500a3SJeff Roberson #ifdef SMP
949cac77d04SJeff Roberson 	balance_groups = 0;
95080f86c9fSJeff Roberson 	/*
95180f86c9fSJeff Roberson 	 * Initialize the kseqs.
95280f86c9fSJeff Roberson 	 */
953749d01b0SJeff Roberson 	for (i = 0; i < MAXCPU; i++) {
95480f86c9fSJeff Roberson 		struct kseq *ksq;
95580f86c9fSJeff Roberson 
95680f86c9fSJeff Roberson 		ksq = &kseq_cpu[i];
95780f86c9fSJeff Roberson 		ksq->ksq_assigned = NULL;
958749d01b0SJeff Roberson 		kseq_setup(&kseq_cpu[i]);
95980f86c9fSJeff Roberson 	}
96080f86c9fSJeff Roberson 	if (smp_topology == NULL) {
96180f86c9fSJeff Roberson 		struct kseq_group *ksg;
96280f86c9fSJeff Roberson 		struct kseq *ksq;
963598b368dSJeff Roberson 		int cpus;
96480f86c9fSJeff Roberson 
965598b368dSJeff Roberson 		for (cpus = 0, i = 0; i < MAXCPU; i++) {
966598b368dSJeff Roberson 			if (CPU_ABSENT(i))
967598b368dSJeff Roberson 				continue;
968598b368dSJeff Roberson 			ksq = &kseq_cpu[cpus];
969598b368dSJeff Roberson 			ksg = &kseq_groups[cpus];
97080f86c9fSJeff Roberson 			/*
971dc03363dSJeff Roberson 			 * Setup a kseq group with one member.
97280f86c9fSJeff Roberson 			 */
97380f86c9fSJeff Roberson 			ksq->ksq_transferable = 0;
97480f86c9fSJeff Roberson 			ksq->ksq_group = ksg;
97580f86c9fSJeff Roberson 			ksg->ksg_cpus = 1;
97680f86c9fSJeff Roberson 			ksg->ksg_idlemask = 0;
97780f86c9fSJeff Roberson 			ksg->ksg_cpumask = ksg->ksg_mask = 1 << i;
978cac77d04SJeff Roberson 			ksg->ksg_load = 0;
97980f86c9fSJeff Roberson 			ksg->ksg_transferable = 0;
98080f86c9fSJeff Roberson 			LIST_INIT(&ksg->ksg_members);
98180f86c9fSJeff Roberson 			LIST_INSERT_HEAD(&ksg->ksg_members, ksq, ksq_siblings);
982598b368dSJeff Roberson 			cpus++;
983749d01b0SJeff Roberson 		}
984598b368dSJeff Roberson 		ksg_maxid = cpus - 1;
985749d01b0SJeff Roberson 	} else {
98680f86c9fSJeff Roberson 		struct kseq_group *ksg;
98780f86c9fSJeff Roberson 		struct cpu_group *cg;
988749d01b0SJeff Roberson 		int j;
989749d01b0SJeff Roberson 
990749d01b0SJeff Roberson 		for (i = 0; i < smp_topology->ct_count; i++) {
991749d01b0SJeff Roberson 			cg = &smp_topology->ct_group[i];
99280f86c9fSJeff Roberson 			ksg = &kseq_groups[i];
99380f86c9fSJeff Roberson 			/*
99480f86c9fSJeff Roberson 			 * Initialize the group.
99580f86c9fSJeff Roberson 			 */
99680f86c9fSJeff Roberson 			ksg->ksg_idlemask = 0;
997cac77d04SJeff Roberson 			ksg->ksg_load = 0;
99880f86c9fSJeff Roberson 			ksg->ksg_transferable = 0;
99980f86c9fSJeff Roberson 			ksg->ksg_cpus = cg->cg_count;
100080f86c9fSJeff Roberson 			ksg->ksg_cpumask = cg->cg_mask;
100180f86c9fSJeff Roberson 			LIST_INIT(&ksg->ksg_members);
100280f86c9fSJeff Roberson 			/*
100380f86c9fSJeff Roberson 			 * Find all of the group members and add them.
100480f86c9fSJeff Roberson 			 */
100580f86c9fSJeff Roberson 			for (j = 0; j < MAXCPU; j++) {
100680f86c9fSJeff Roberson 				if ((cg->cg_mask & (1 << j)) != 0) {
100780f86c9fSJeff Roberson 					if (ksg->ksg_mask == 0)
100880f86c9fSJeff Roberson 						ksg->ksg_mask = 1 << j;
100980f86c9fSJeff Roberson 					kseq_cpu[j].ksq_transferable = 0;
101080f86c9fSJeff Roberson 					kseq_cpu[j].ksq_group = ksg;
101180f86c9fSJeff Roberson 					LIST_INSERT_HEAD(&ksg->ksg_members,
101280f86c9fSJeff Roberson 					    &kseq_cpu[j], ksq_siblings);
101380f86c9fSJeff Roberson 				}
101480f86c9fSJeff Roberson 			}
1015cac77d04SJeff Roberson 			if (ksg->ksg_cpus > 1)
1016cac77d04SJeff Roberson 				balance_groups = 1;
1017749d01b0SJeff Roberson 		}
1018cac77d04SJeff Roberson 		ksg_maxid = smp_topology->ct_count - 1;
1019749d01b0SJeff Roberson 	}
1020cac77d04SJeff Roberson 	/*
1021cac77d04SJeff Roberson 	 * Stagger the group and global load balancer so they do not
1022cac77d04SJeff Roberson 	 * interfere with each other.
1023cac77d04SJeff Roberson 	 */
1024dc03363dSJeff Roberson 	bal_tick = ticks + hz;
1025cac77d04SJeff Roberson 	if (balance_groups)
1026dc03363dSJeff Roberson 		gbal_tick = ticks + (hz / 2);
1027749d01b0SJeff Roberson #else
1028749d01b0SJeff Roberson 	kseq_setup(KSEQ_SELF());
1029356500a3SJeff Roberson #endif
1030749d01b0SJeff Roberson 	mtx_lock_spin(&sched_lock);
1031155b9987SJeff Roberson 	kseq_load_add(KSEQ_SELF(), &kse0);
1032749d01b0SJeff Roberson 	mtx_unlock_spin(&sched_lock);
103335e6168fSJeff Roberson }
103435e6168fSJeff Roberson 
103535e6168fSJeff Roberson /*
103635e6168fSJeff Roberson  * Scale the scheduling priority according to the "interactivity" of this
103735e6168fSJeff Roberson  * process.
103835e6168fSJeff Roberson  */
103915dc847eSJeff Roberson static void
104035e6168fSJeff Roberson sched_priority(struct ksegrp *kg)
104135e6168fSJeff Roberson {
104235e6168fSJeff Roberson 	int pri;
104335e6168fSJeff Roberson 
104435e6168fSJeff Roberson 	if (kg->kg_pri_class != PRI_TIMESHARE)
104515dc847eSJeff Roberson 		return;
104635e6168fSJeff Roberson 
104715dc847eSJeff Roberson 	pri = SCHED_PRI_INTERACT(sched_interact_score(kg));
1048e1f89c22SJeff Roberson 	pri += SCHED_PRI_BASE;
1049fa885116SJulian Elischer 	pri += kg->kg_proc->p_nice;
105035e6168fSJeff Roberson 
105135e6168fSJeff Roberson 	if (pri > PRI_MAX_TIMESHARE)
105235e6168fSJeff Roberson 		pri = PRI_MAX_TIMESHARE;
105335e6168fSJeff Roberson 	else if (pri < PRI_MIN_TIMESHARE)
105435e6168fSJeff Roberson 		pri = PRI_MIN_TIMESHARE;
105535e6168fSJeff Roberson 
105635e6168fSJeff Roberson 	kg->kg_user_pri = pri;
105735e6168fSJeff Roberson 
105815dc847eSJeff Roberson 	return;
105935e6168fSJeff Roberson }
106035e6168fSJeff Roberson 
106135e6168fSJeff Roberson /*
1062245f3abfSJeff Roberson  * Calculate a time slice based on the properties of the kseg and the runq
1063a8949de2SJeff Roberson  * that we're on.  This is only for PRI_TIMESHARE ksegrps.
106435e6168fSJeff Roberson  */
1065245f3abfSJeff Roberson static void
1066245f3abfSJeff Roberson sched_slice(struct kse *ke)
106735e6168fSJeff Roberson {
106815dc847eSJeff Roberson 	struct kseq *kseq;
1069245f3abfSJeff Roberson 	struct ksegrp *kg;
107035e6168fSJeff Roberson 
1071245f3abfSJeff Roberson 	kg = ke->ke_ksegrp;
107215dc847eSJeff Roberson 	kseq = KSEQ_CPU(ke->ke_cpu);
107335e6168fSJeff Roberson 
1074f5c157d9SJohn Baldwin 	if (ke->ke_thread->td_flags & TDF_BORROWING) {
10758ffb8f55SJeff Roberson 		ke->ke_slice = SCHED_SLICE_MIN;
10768ffb8f55SJeff Roberson 		return;
10778ffb8f55SJeff Roberson 	}
10788ffb8f55SJeff Roberson 
1079245f3abfSJeff Roberson 	/*
1080245f3abfSJeff Roberson 	 * Rationale:
10812454aaf5SJeff Roberson 	 * KSEs in interactive ksegs get a minimal slice so that we
1082245f3abfSJeff Roberson 	 * quickly notice if it abuses its advantage.
1083245f3abfSJeff Roberson 	 *
1084245f3abfSJeff Roberson 	 * KSEs in non-interactive ksegs are assigned a slice that is
1085245f3abfSJeff Roberson 	 * based on the ksegs nice value relative to the least nice kseg
1086245f3abfSJeff Roberson 	 * on the run queue for this cpu.
1087245f3abfSJeff Roberson 	 *
1088245f3abfSJeff Roberson 	 * If the KSE is less nice than all others it gets the maximum
1089245f3abfSJeff Roberson 	 * slice and other KSEs will adjust their slice relative to
1090245f3abfSJeff Roberson 	 * this when they first expire.
1091245f3abfSJeff Roberson 	 *
1092245f3abfSJeff Roberson 	 * There is 20 point window that starts relative to the least
1093245f3abfSJeff Roberson 	 * nice kse on the run queue.  Slice size is determined by
1094245f3abfSJeff Roberson 	 * the kse distance from the last nice ksegrp.
1095245f3abfSJeff Roberson 	 *
10967d1a81b4SJeff Roberson 	 * If the kse is outside of the window it will get no slice
10977d1a81b4SJeff Roberson 	 * and will be reevaluated each time it is selected on the
10987d1a81b4SJeff Roberson 	 * run queue.  The exception to this is nice 0 ksegs when
10997d1a81b4SJeff Roberson 	 * a nice -20 is running.  They are always granted a minimum
11007d1a81b4SJeff Roberson 	 * slice.
1101245f3abfSJeff Roberson 	 */
110215dc847eSJeff Roberson 	if (!SCHED_INTERACTIVE(kg)) {
1103245f3abfSJeff Roberson 		int nice;
1104245f3abfSJeff Roberson 
1105fa885116SJulian Elischer 		nice = kg->kg_proc->p_nice + (0 - kseq->ksq_nicemin);
1106ef1134c9SJeff Roberson 		if (kseq->ksq_load_timeshare == 0 ||
1107fa885116SJulian Elischer 		    kg->kg_proc->p_nice < kseq->ksq_nicemin)
1108245f3abfSJeff Roberson 			ke->ke_slice = SCHED_SLICE_MAX;
11097d1a81b4SJeff Roberson 		else if (nice <= SCHED_SLICE_NTHRESH)
1110245f3abfSJeff Roberson 			ke->ke_slice = SCHED_SLICE_NICE(nice);
1111fa885116SJulian Elischer 		else if (kg->kg_proc->p_nice == 0)
11127d1a81b4SJeff Roberson 			ke->ke_slice = SCHED_SLICE_MIN;
1113245f3abfSJeff Roberson 		else
1114245f3abfSJeff Roberson 			ke->ke_slice = 0;
1115245f3abfSJeff Roberson 	} else
11169b5f6f62SJeff Roberson 		ke->ke_slice = SCHED_SLICE_INTERACTIVE;
111735e6168fSJeff Roberson 
1118245f3abfSJeff Roberson 	return;
111935e6168fSJeff Roberson }
112035e6168fSJeff Roberson 
1121d322132cSJeff Roberson /*
1122d322132cSJeff Roberson  * This routine enforces a maximum limit on the amount of scheduling history
1123d322132cSJeff Roberson  * kept.  It is called after either the slptime or runtime is adjusted.
1124d322132cSJeff Roberson  * This routine will not operate correctly when slp or run times have been
1125d322132cSJeff Roberson  * adjusted to more than double their maximum.
1126d322132cSJeff Roberson  */
11274b60e324SJeff Roberson static void
11284b60e324SJeff Roberson sched_interact_update(struct ksegrp *kg)
11294b60e324SJeff Roberson {
1130d322132cSJeff Roberson 	int sum;
11313f741ca1SJeff Roberson 
1132d322132cSJeff Roberson 	sum = kg->kg_runtime + kg->kg_slptime;
1133d322132cSJeff Roberson 	if (sum < SCHED_SLP_RUN_MAX)
1134d322132cSJeff Roberson 		return;
1135d322132cSJeff Roberson 	/*
1136d322132cSJeff Roberson 	 * If we have exceeded by more than 1/5th then the algorithm below
1137d322132cSJeff Roberson 	 * will not bring us back into range.  Dividing by two here forces
11382454aaf5SJeff Roberson 	 * us into the range of [4/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX]
1139d322132cSJeff Roberson 	 */
114037a35e4aSJeff Roberson 	if (sum > (SCHED_SLP_RUN_MAX / 5) * 6) {
1141d322132cSJeff Roberson 		kg->kg_runtime /= 2;
1142d322132cSJeff Roberson 		kg->kg_slptime /= 2;
1143d322132cSJeff Roberson 		return;
1144d322132cSJeff Roberson 	}
1145d322132cSJeff Roberson 	kg->kg_runtime = (kg->kg_runtime / 5) * 4;
1146d322132cSJeff Roberson 	kg->kg_slptime = (kg->kg_slptime / 5) * 4;
1147d322132cSJeff Roberson }
1148d322132cSJeff Roberson 
1149d322132cSJeff Roberson static void
1150d322132cSJeff Roberson sched_interact_fork(struct ksegrp *kg)
1151d322132cSJeff Roberson {
1152d322132cSJeff Roberson 	int ratio;
1153d322132cSJeff Roberson 	int sum;
1154d322132cSJeff Roberson 
1155d322132cSJeff Roberson 	sum = kg->kg_runtime + kg->kg_slptime;
1156d322132cSJeff Roberson 	if (sum > SCHED_SLP_RUN_FORK) {
1157d322132cSJeff Roberson 		ratio = sum / SCHED_SLP_RUN_FORK;
1158d322132cSJeff Roberson 		kg->kg_runtime /= ratio;
1159d322132cSJeff Roberson 		kg->kg_slptime /= ratio;
11604b60e324SJeff Roberson 	}
11614b60e324SJeff Roberson }
11624b60e324SJeff Roberson 
1163e1f89c22SJeff Roberson static int
1164e1f89c22SJeff Roberson sched_interact_score(struct ksegrp *kg)
1165e1f89c22SJeff Roberson {
1166210491d3SJeff Roberson 	int div;
1167e1f89c22SJeff Roberson 
1168e1f89c22SJeff Roberson 	if (kg->kg_runtime > kg->kg_slptime) {
1169210491d3SJeff Roberson 		div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF);
1170210491d3SJeff Roberson 		return (SCHED_INTERACT_HALF +
1171210491d3SJeff Roberson 		    (SCHED_INTERACT_HALF - (kg->kg_slptime / div)));
1172210491d3SJeff Roberson 	} if (kg->kg_slptime > kg->kg_runtime) {
1173210491d3SJeff Roberson 		div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF);
1174210491d3SJeff Roberson 		return (kg->kg_runtime / div);
1175e1f89c22SJeff Roberson 	}
1176e1f89c22SJeff Roberson 
1177210491d3SJeff Roberson 	/*
1178210491d3SJeff Roberson 	 * This can happen if slptime and runtime are 0.
1179210491d3SJeff Roberson 	 */
1180210491d3SJeff Roberson 	return (0);
1181e1f89c22SJeff Roberson 
1182e1f89c22SJeff Roberson }
1183e1f89c22SJeff Roberson 
118415dc847eSJeff Roberson /*
1185ed062c8dSJulian Elischer  * Very early in the boot some setup of scheduler-specific
1186ed062c8dSJulian Elischer  * parts of proc0 and of soem scheduler resources needs to be done.
1187ed062c8dSJulian Elischer  * Called from:
1188ed062c8dSJulian Elischer  *  proc0_init()
1189ed062c8dSJulian Elischer  */
1190ed062c8dSJulian Elischer void
1191ed062c8dSJulian Elischer schedinit(void)
1192ed062c8dSJulian Elischer {
1193ed062c8dSJulian Elischer 	/*
1194ed062c8dSJulian Elischer 	 * Set up the scheduler specific parts of proc0.
1195ed062c8dSJulian Elischer 	 */
1196ed062c8dSJulian Elischer 	proc0.p_sched = NULL; /* XXX */
1197d39063f2SJulian Elischer 	ksegrp0.kg_sched = &kg_sched0;
1198d39063f2SJulian Elischer 	thread0.td_sched = &kse0;
1199ed062c8dSJulian Elischer 	kse0.ke_thread = &thread0;
1200ed062c8dSJulian Elischer 	kse0.ke_state = KES_THREAD;
1201ed062c8dSJulian Elischer 	kg_sched0.skg_concurrency = 1;
1202ed062c8dSJulian Elischer 	kg_sched0.skg_avail_opennings = 0; /* we are already running */
1203ed062c8dSJulian Elischer }
1204ed062c8dSJulian Elischer 
1205ed062c8dSJulian Elischer /*
120615dc847eSJeff Roberson  * This is only somewhat accurate since given many processes of the same
120715dc847eSJeff Roberson  * priority they will switch when their slices run out, which will be
120815dc847eSJeff Roberson  * at most SCHED_SLICE_MAX.
120915dc847eSJeff Roberson  */
121035e6168fSJeff Roberson int
121135e6168fSJeff Roberson sched_rr_interval(void)
121235e6168fSJeff Roberson {
121335e6168fSJeff Roberson 	return (SCHED_SLICE_MAX);
121435e6168fSJeff Roberson }
121535e6168fSJeff Roberson 
121622bf7d9aSJeff Roberson static void
121735e6168fSJeff Roberson sched_pctcpu_update(struct kse *ke)
121835e6168fSJeff Roberson {
121935e6168fSJeff Roberson 	/*
122035e6168fSJeff Roberson 	 * Adjust counters and watermark for pctcpu calc.
1221210491d3SJeff Roberson 	 */
122281de51bfSJeff Roberson 	if (ke->ke_ltick > ticks - SCHED_CPU_TICKS) {
1223210491d3SJeff Roberson 		/*
122481de51bfSJeff Roberson 		 * Shift the tick count out so that the divide doesn't
122581de51bfSJeff Roberson 		 * round away our results.
122665c8760dSJeff Roberson 		 */
122765c8760dSJeff Roberson 		ke->ke_ticks <<= 10;
122881de51bfSJeff Roberson 		ke->ke_ticks = (ke->ke_ticks / (ticks - ke->ke_ftick)) *
122935e6168fSJeff Roberson 			    SCHED_CPU_TICKS;
123065c8760dSJeff Roberson 		ke->ke_ticks >>= 10;
123181de51bfSJeff Roberson 	} else
123281de51bfSJeff Roberson 		ke->ke_ticks = 0;
123335e6168fSJeff Roberson 	ke->ke_ltick = ticks;
123435e6168fSJeff Roberson 	ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS;
123535e6168fSJeff Roberson }
123635e6168fSJeff Roberson 
123735e6168fSJeff Roberson void
1238f5c157d9SJohn Baldwin sched_thread_priority(struct thread *td, u_char prio)
123935e6168fSJeff Roberson {
12403f741ca1SJeff Roberson 	struct kse *ke;
124135e6168fSJeff Roberson 
124281d47d3fSJeff Roberson 	CTR6(KTR_SCHED, "sched_prio: %p(%s) prio %d newprio %d by %p(%s)",
124381d47d3fSJeff Roberson 	    td, td->td_proc->p_comm, td->td_priority, prio, curthread,
124481d47d3fSJeff Roberson 	    curthread->td_proc->p_comm);
12453f741ca1SJeff Roberson 	ke = td->td_kse;
124635e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
1247f5c157d9SJohn Baldwin 	if (td->td_priority == prio)
1248f5c157d9SJohn Baldwin 		return;
124935e6168fSJeff Roberson 	if (TD_ON_RUNQ(td)) {
12503f741ca1SJeff Roberson 		/*
12513f741ca1SJeff Roberson 		 * If the priority has been elevated due to priority
12523f741ca1SJeff Roberson 		 * propagation, we may have to move ourselves to a new
12533f741ca1SJeff Roberson 		 * queue.  We still call adjustrunqueue below in case kse
12543f741ca1SJeff Roberson 		 * needs to fix things up.
12553f741ca1SJeff Roberson 		 */
12568ffb8f55SJeff Roberson 		if (prio < td->td_priority && ke->ke_runq != NULL &&
1257769a3635SJeff Roberson 		    (ke->ke_flags & KEF_ASSIGNED) == 0 &&
125822bf7d9aSJeff Roberson 		    ke->ke_runq != KSEQ_CPU(ke->ke_cpu)->ksq_curr) {
12593f741ca1SJeff Roberson 			runq_remove(ke->ke_runq, ke);
12603f741ca1SJeff Roberson 			ke->ke_runq = KSEQ_CPU(ke->ke_cpu)->ksq_curr;
1261c20c691bSJulian Elischer 			runq_add(ke->ke_runq, ke, 0);
126235e6168fSJeff Roberson 		}
1263f2b74cbfSJeff Roberson 		/*
1264f2b74cbfSJeff Roberson 		 * Hold this kse on this cpu so that sched_prio() doesn't
1265f2b74cbfSJeff Roberson 		 * cause excessive migration.  We only want migration to
1266f2b74cbfSJeff Roberson 		 * happen as the result of a wakeup.
1267f2b74cbfSJeff Roberson 		 */
1268f2b74cbfSJeff Roberson 		ke->ke_flags |= KEF_HOLD;
12693f741ca1SJeff Roberson 		adjustrunqueue(td, prio);
1270598b368dSJeff Roberson 		ke->ke_flags &= ~KEF_HOLD;
12713f741ca1SJeff Roberson 	} else
12723f741ca1SJeff Roberson 		td->td_priority = prio;
127335e6168fSJeff Roberson }
127435e6168fSJeff Roberson 
1275f5c157d9SJohn Baldwin /*
1276f5c157d9SJohn Baldwin  * Update a thread's priority when it is lent another thread's
1277f5c157d9SJohn Baldwin  * priority.
1278f5c157d9SJohn Baldwin  */
1279f5c157d9SJohn Baldwin void
1280f5c157d9SJohn Baldwin sched_lend_prio(struct thread *td, u_char prio)
1281f5c157d9SJohn Baldwin {
1282f5c157d9SJohn Baldwin 
1283f5c157d9SJohn Baldwin 	td->td_flags |= TDF_BORROWING;
1284f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1285f5c157d9SJohn Baldwin }
1286f5c157d9SJohn Baldwin 
1287f5c157d9SJohn Baldwin /*
1288f5c157d9SJohn Baldwin  * Restore a thread's priority when priority propagation is
1289f5c157d9SJohn Baldwin  * over.  The prio argument is the minimum priority the thread
1290f5c157d9SJohn Baldwin  * needs to have to satisfy other possible priority lending
1291f5c157d9SJohn Baldwin  * requests.  If the thread's regular priority is less
1292f5c157d9SJohn Baldwin  * important than prio, the thread will keep a priority boost
1293f5c157d9SJohn Baldwin  * of prio.
1294f5c157d9SJohn Baldwin  */
1295f5c157d9SJohn Baldwin void
1296f5c157d9SJohn Baldwin sched_unlend_prio(struct thread *td, u_char prio)
1297f5c157d9SJohn Baldwin {
1298f5c157d9SJohn Baldwin 	u_char base_pri;
1299f5c157d9SJohn Baldwin 
1300f5c157d9SJohn Baldwin 	if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
1301f5c157d9SJohn Baldwin 	    td->td_base_pri <= PRI_MAX_TIMESHARE)
1302f5c157d9SJohn Baldwin 		base_pri = td->td_ksegrp->kg_user_pri;
1303f5c157d9SJohn Baldwin 	else
1304f5c157d9SJohn Baldwin 		base_pri = td->td_base_pri;
1305f5c157d9SJohn Baldwin 	if (prio >= base_pri) {
1306f5c157d9SJohn Baldwin 		td->td_flags &= ~TDF_BORROWING;
1307f5c157d9SJohn Baldwin 		sched_thread_priority(td, base_pri);
1308f5c157d9SJohn Baldwin 	} else
1309f5c157d9SJohn Baldwin 		sched_lend_prio(td, prio);
1310f5c157d9SJohn Baldwin }
1311f5c157d9SJohn Baldwin 
1312f5c157d9SJohn Baldwin void
1313f5c157d9SJohn Baldwin sched_prio(struct thread *td, u_char prio)
1314f5c157d9SJohn Baldwin {
1315f5c157d9SJohn Baldwin 	u_char oldprio;
1316f5c157d9SJohn Baldwin 
1317f5c157d9SJohn Baldwin 	/* First, update the base priority. */
1318f5c157d9SJohn Baldwin 	td->td_base_pri = prio;
1319f5c157d9SJohn Baldwin 
1320f5c157d9SJohn Baldwin 	/*
132150aaa791SJohn Baldwin 	 * If the thread is borrowing another thread's priority, don't
1322f5c157d9SJohn Baldwin 	 * ever lower the priority.
1323f5c157d9SJohn Baldwin 	 */
1324f5c157d9SJohn Baldwin 	if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
1325f5c157d9SJohn Baldwin 		return;
1326f5c157d9SJohn Baldwin 
1327f5c157d9SJohn Baldwin 	/* Change the real priority. */
1328f5c157d9SJohn Baldwin 	oldprio = td->td_priority;
1329f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1330f5c157d9SJohn Baldwin 
1331f5c157d9SJohn Baldwin 	/*
1332f5c157d9SJohn Baldwin 	 * If the thread is on a turnstile, then let the turnstile update
1333f5c157d9SJohn Baldwin 	 * its state.
1334f5c157d9SJohn Baldwin 	 */
1335f5c157d9SJohn Baldwin 	if (TD_ON_LOCK(td) && oldprio != prio)
1336f5c157d9SJohn Baldwin 		turnstile_adjust(td, oldprio);
1337f5c157d9SJohn Baldwin }
1338f5c157d9SJohn Baldwin 
133935e6168fSJeff Roberson void
13403389af30SJulian Elischer sched_switch(struct thread *td, struct thread *newtd, int flags)
134135e6168fSJeff Roberson {
1342598b368dSJeff Roberson 	struct kseq *ksq;
134335e6168fSJeff Roberson 	struct kse *ke;
134435e6168fSJeff Roberson 
134535e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
134635e6168fSJeff Roberson 
134735e6168fSJeff Roberson 	ke = td->td_kse;
1348598b368dSJeff Roberson 	ksq = KSEQ_SELF();
134935e6168fSJeff Roberson 
1350060563ecSJulian Elischer 	td->td_lastcpu = td->td_oncpu;
1351060563ecSJulian Elischer 	td->td_oncpu = NOCPU;
135252eb8464SJohn Baldwin 	td->td_flags &= ~TDF_NEEDRESCHED;
135377918643SStephan Uphoff 	td->td_owepreempt = 0;
135435e6168fSJeff Roberson 
1355b11fdad0SJeff Roberson 	/*
1356b11fdad0SJeff Roberson 	 * If the KSE has been assigned it may be in the process of switching
1357b11fdad0SJeff Roberson 	 * to the new cpu.  This is the case in sched_bind().
1358b11fdad0SJeff Roberson 	 */
13592454aaf5SJeff Roberson 	if (td == PCPU_GET(idlethread)) {
1360bf0acc27SJohn Baldwin 		TD_SET_CAN_RUN(td);
1361598b368dSJeff Roberson 	} else if ((ke->ke_flags & KEF_ASSIGNED) == 0) {
1362ed062c8dSJulian Elischer 		/* We are ending our run so make our slot available again */
1363d39063f2SJulian Elischer 		SLOT_RELEASE(td->td_ksegrp);
1364598b368dSJeff Roberson 		kseq_load_rem(ksq, ke);
1365ed062c8dSJulian Elischer 		if (TD_IS_RUNNING(td)) {
1366f2b74cbfSJeff Roberson 			/*
1367ed062c8dSJulian Elischer 			 * Don't allow the thread to migrate
1368ed062c8dSJulian Elischer 			 * from a preemption.
1369f2b74cbfSJeff Roberson 			 */
1370f2b74cbfSJeff Roberson 			ke->ke_flags |= KEF_HOLD;
1371598b368dSJeff Roberson 			setrunqueue(td, (flags & SW_PREEMPT) ?
1372598b368dSJeff Roberson 			    SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
1373598b368dSJeff Roberson 			    SRQ_OURSELF|SRQ_YIELDING);
1374598b368dSJeff Roberson 			ke->ke_flags &= ~KEF_HOLD;
1375598b368dSJeff Roberson 		} else if ((td->td_proc->p_flag & P_HADTHREADS) &&
1376598b368dSJeff Roberson 		    (newtd == NULL || newtd->td_ksegrp != td->td_ksegrp))
137735e6168fSJeff Roberson 			/*
1378ed062c8dSJulian Elischer 			 * We will not be on the run queue.
1379ed062c8dSJulian Elischer 			 * So we must be sleeping or similar.
1380c20c691bSJulian Elischer 			 * Don't use the slot if we will need it
1381c20c691bSJulian Elischer 			 * for newtd.
138235e6168fSJeff Roberson 			 */
1383ed062c8dSJulian Elischer 			slot_fill(td->td_ksegrp);
1384ed062c8dSJulian Elischer 	}
1385d39063f2SJulian Elischer 	if (newtd != NULL) {
1386c20c691bSJulian Elischer 		/*
1387c20c691bSJulian Elischer 		 * If we bring in a thread,
1388c20c691bSJulian Elischer 		 * then account for it as if it had been added to the
1389c20c691bSJulian Elischer 		 * run queue and then chosen.
1390c20c691bSJulian Elischer 		 */
1391c5c3fb33SJulian Elischer 		newtd->td_kse->ke_flags |= KEF_DIDRUN;
1392598b368dSJeff Roberson 		newtd->td_kse->ke_runq = ksq->ksq_curr;
1393d39063f2SJulian Elischer 		SLOT_USE(newtd->td_ksegrp);
1394c20c691bSJulian Elischer 		TD_SET_RUNNING(newtd);
1395bf0acc27SJohn Baldwin 		kseq_load_add(KSEQ_SELF(), newtd->td_kse);
1396d39063f2SJulian Elischer 	} else
13972454aaf5SJeff Roberson 		newtd = choosethread();
1398ebccf1e3SJoseph Koshy 	if (td != newtd) {
1399ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
1400ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1401ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
1402ebccf1e3SJoseph Koshy #endif
1403ae53b483SJeff Roberson 		cpu_switch(td, newtd);
1404ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
1405ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1406ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
1407ebccf1e3SJoseph Koshy #endif
1408ebccf1e3SJoseph Koshy 	}
1409ebccf1e3SJoseph Koshy 
1410ae53b483SJeff Roberson 	sched_lock.mtx_lock = (uintptr_t)td;
141135e6168fSJeff Roberson 
1412060563ecSJulian Elischer 	td->td_oncpu = PCPU_GET(cpuid);
141335e6168fSJeff Roberson }
141435e6168fSJeff Roberson 
141535e6168fSJeff Roberson void
1416fa885116SJulian Elischer sched_nice(struct proc *p, int nice)
141735e6168fSJeff Roberson {
1418fa885116SJulian Elischer 	struct ksegrp *kg;
141915dc847eSJeff Roberson 	struct kse *ke;
142035e6168fSJeff Roberson 	struct thread *td;
142115dc847eSJeff Roberson 	struct kseq *kseq;
142235e6168fSJeff Roberson 
1423fa885116SJulian Elischer 	PROC_LOCK_ASSERT(p, MA_OWNED);
14240b5318c8SJohn Baldwin 	mtx_assert(&sched_lock, MA_OWNED);
142515dc847eSJeff Roberson 	/*
142615dc847eSJeff Roberson 	 * We need to adjust the nice counts for running KSEs.
142715dc847eSJeff Roberson 	 */
1428fa885116SJulian Elischer 	FOREACH_KSEGRP_IN_PROC(p, kg) {
1429fa885116SJulian Elischer 		if (kg->kg_pri_class == PRI_TIMESHARE) {
1430ed062c8dSJulian Elischer 			FOREACH_THREAD_IN_GROUP(kg, td) {
1431ed062c8dSJulian Elischer 				ke = td->td_kse;
1432d07ac847SJeff Roberson 				if (ke->ke_runq == NULL)
143315dc847eSJeff Roberson 					continue;
143415dc847eSJeff Roberson 				kseq = KSEQ_CPU(ke->ke_cpu);
1435fa885116SJulian Elischer 				kseq_nice_rem(kseq, p->p_nice);
143615dc847eSJeff Roberson 				kseq_nice_add(kseq, nice);
143715dc847eSJeff Roberson 			}
1438fa885116SJulian Elischer 		}
1439fa885116SJulian Elischer 	}
1440fa885116SJulian Elischer 	p->p_nice = nice;
1441fa885116SJulian Elischer 	FOREACH_KSEGRP_IN_PROC(p, kg) {
144235e6168fSJeff Roberson 		sched_priority(kg);
144315dc847eSJeff Roberson 		FOREACH_THREAD_IN_GROUP(kg, td)
14444a338afdSJulian Elischer 			td->td_flags |= TDF_NEEDRESCHED;
144535e6168fSJeff Roberson 	}
1446fa885116SJulian Elischer }
144735e6168fSJeff Roberson 
144835e6168fSJeff Roberson void
144944f3b092SJohn Baldwin sched_sleep(struct thread *td)
145035e6168fSJeff Roberson {
145135e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
145235e6168fSJeff Roberson 
145335e6168fSJeff Roberson 	td->td_slptime = ticks;
145435e6168fSJeff Roberson }
145535e6168fSJeff Roberson 
145635e6168fSJeff Roberson void
145735e6168fSJeff Roberson sched_wakeup(struct thread *td)
145835e6168fSJeff Roberson {
145935e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
146035e6168fSJeff Roberson 
146135e6168fSJeff Roberson 	/*
146235e6168fSJeff Roberson 	 * Let the kseg know how long we slept for.  This is because process
146335e6168fSJeff Roberson 	 * interactivity behavior is modeled in the kseg.
146435e6168fSJeff Roberson 	 */
146535e6168fSJeff Roberson 	if (td->td_slptime) {
1466f1e8dc4aSJeff Roberson 		struct ksegrp *kg;
146715dc847eSJeff Roberson 		int hzticks;
1468f1e8dc4aSJeff Roberson 
1469f1e8dc4aSJeff Roberson 		kg = td->td_ksegrp;
1470d322132cSJeff Roberson 		hzticks = (ticks - td->td_slptime) << 10;
1471d322132cSJeff Roberson 		if (hzticks >= SCHED_SLP_RUN_MAX) {
1472d322132cSJeff Roberson 			kg->kg_slptime = SCHED_SLP_RUN_MAX;
1473d322132cSJeff Roberson 			kg->kg_runtime = 1;
1474d322132cSJeff Roberson 		} else {
1475d322132cSJeff Roberson 			kg->kg_slptime += hzticks;
14764b60e324SJeff Roberson 			sched_interact_update(kg);
1477d322132cSJeff Roberson 		}
1478f1e8dc4aSJeff Roberson 		sched_priority(kg);
14794b60e324SJeff Roberson 		sched_slice(td->td_kse);
148035e6168fSJeff Roberson 		td->td_slptime = 0;
1481f1e8dc4aSJeff Roberson 	}
14822630e4c9SJulian Elischer 	setrunqueue(td, SRQ_BORING);
148335e6168fSJeff Roberson }
148435e6168fSJeff Roberson 
148535e6168fSJeff Roberson /*
148635e6168fSJeff Roberson  * Penalize the parent for creating a new child and initialize the child's
148735e6168fSJeff Roberson  * priority.
148835e6168fSJeff Roberson  */
148935e6168fSJeff Roberson void
1490ed062c8dSJulian Elischer sched_fork(struct thread *td, struct thread *childtd)
149135e6168fSJeff Roberson {
149235e6168fSJeff Roberson 
149335e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
149435e6168fSJeff Roberson 
1495ed062c8dSJulian Elischer 	sched_fork_ksegrp(td, childtd->td_ksegrp);
1496ed062c8dSJulian Elischer 	sched_fork_thread(td, childtd);
149715dc847eSJeff Roberson }
149815dc847eSJeff Roberson 
149915dc847eSJeff Roberson void
150055d44f79SJulian Elischer sched_fork_ksegrp(struct thread *td, struct ksegrp *child)
150115dc847eSJeff Roberson {
150255d44f79SJulian Elischer 	struct ksegrp *kg = td->td_ksegrp;
1503ed062c8dSJulian Elischer 	mtx_assert(&sched_lock, MA_OWNED);
1504210491d3SJeff Roberson 
1505d322132cSJeff Roberson 	child->kg_slptime = kg->kg_slptime;
1506d322132cSJeff Roberson 	child->kg_runtime = kg->kg_runtime;
1507d322132cSJeff Roberson 	child->kg_user_pri = kg->kg_user_pri;
1508d322132cSJeff Roberson 	sched_interact_fork(child);
15094b60e324SJeff Roberson 	kg->kg_runtime += tickincr << 10;
15104b60e324SJeff Roberson 	sched_interact_update(kg);
1511c9f25d8fSJeff Roberson }
1512c9f25d8fSJeff Roberson 
151315dc847eSJeff Roberson void
151415dc847eSJeff Roberson sched_fork_thread(struct thread *td, struct thread *child)
151515dc847eSJeff Roberson {
1516ed062c8dSJulian Elischer 	struct kse *ke;
1517ed062c8dSJulian Elischer 	struct kse *ke2;
1518ed062c8dSJulian Elischer 
1519ed062c8dSJulian Elischer 	sched_newthread(child);
1520ed062c8dSJulian Elischer 	ke = td->td_kse;
1521ed062c8dSJulian Elischer 	ke2 = child->td_kse;
1522ed062c8dSJulian Elischer 	ke2->ke_slice = 1;	/* Attempt to quickly learn interactivity. */
1523ed062c8dSJulian Elischer 	ke2->ke_cpu = ke->ke_cpu;
1524ed062c8dSJulian Elischer 	ke2->ke_runq = NULL;
1525ed062c8dSJulian Elischer 
1526ed062c8dSJulian Elischer 	/* Grab our parents cpu estimation information. */
1527ed062c8dSJulian Elischer 	ke2->ke_ticks = ke->ke_ticks;
1528ed062c8dSJulian Elischer 	ke2->ke_ltick = ke->ke_ltick;
1529ed062c8dSJulian Elischer 	ke2->ke_ftick = ke->ke_ftick;
153015dc847eSJeff Roberson }
153115dc847eSJeff Roberson 
153215dc847eSJeff Roberson void
153315dc847eSJeff Roberson sched_class(struct ksegrp *kg, int class)
153415dc847eSJeff Roberson {
153515dc847eSJeff Roberson 	struct kseq *kseq;
153615dc847eSJeff Roberson 	struct kse *ke;
1537ed062c8dSJulian Elischer 	struct thread *td;
1538ef1134c9SJeff Roberson 	int nclass;
1539ef1134c9SJeff Roberson 	int oclass;
154015dc847eSJeff Roberson 
15412056d0a1SJohn Baldwin 	mtx_assert(&sched_lock, MA_OWNED);
154215dc847eSJeff Roberson 	if (kg->kg_pri_class == class)
154315dc847eSJeff Roberson 		return;
154415dc847eSJeff Roberson 
1545ef1134c9SJeff Roberson 	nclass = PRI_BASE(class);
1546ef1134c9SJeff Roberson 	oclass = PRI_BASE(kg->kg_pri_class);
1547ed062c8dSJulian Elischer 	FOREACH_THREAD_IN_GROUP(kg, td) {
1548ed062c8dSJulian Elischer 		ke = td->td_kse;
154942a29039SJeff Roberson 		if ((ke->ke_state != KES_ONRUNQ &&
155042a29039SJeff Roberson 		    ke->ke_state != KES_THREAD) || ke->ke_runq == NULL)
155115dc847eSJeff Roberson 			continue;
155215dc847eSJeff Roberson 		kseq = KSEQ_CPU(ke->ke_cpu);
155315dc847eSJeff Roberson 
1554ef1134c9SJeff Roberson #ifdef SMP
1555155b9987SJeff Roberson 		/*
1556155b9987SJeff Roberson 		 * On SMP if we're on the RUNQ we must adjust the transferable
1557155b9987SJeff Roberson 		 * count because could be changing to or from an interrupt
1558155b9987SJeff Roberson 		 * class.
1559155b9987SJeff Roberson 		 */
1560155b9987SJeff Roberson 		if (ke->ke_state == KES_ONRUNQ) {
1561598b368dSJeff Roberson 			if (KSE_CAN_MIGRATE(ke)) {
156280f86c9fSJeff Roberson 				kseq->ksq_transferable--;
156380f86c9fSJeff Roberson 				kseq->ksq_group->ksg_transferable--;
156480f86c9fSJeff Roberson 			}
1565598b368dSJeff Roberson 			if (KSE_CAN_MIGRATE(ke)) {
156680f86c9fSJeff Roberson 				kseq->ksq_transferable++;
156780f86c9fSJeff Roberson 				kseq->ksq_group->ksg_transferable++;
156880f86c9fSJeff Roberson 			}
1569155b9987SJeff Roberson 		}
1570ef1134c9SJeff Roberson #endif
1571155b9987SJeff Roberson 		if (oclass == PRI_TIMESHARE) {
1572ef1134c9SJeff Roberson 			kseq->ksq_load_timeshare--;
1573fa885116SJulian Elischer 			kseq_nice_rem(kseq, kg->kg_proc->p_nice);
1574155b9987SJeff Roberson 		}
1575155b9987SJeff Roberson 		if (nclass == PRI_TIMESHARE) {
1576155b9987SJeff Roberson 			kseq->ksq_load_timeshare++;
1577fa885116SJulian Elischer 			kseq_nice_add(kseq, kg->kg_proc->p_nice);
157815dc847eSJeff Roberson 		}
1579155b9987SJeff Roberson 	}
158015dc847eSJeff Roberson 
158115dc847eSJeff Roberson 	kg->kg_pri_class = class;
158235e6168fSJeff Roberson }
158335e6168fSJeff Roberson 
158435e6168fSJeff Roberson /*
158535e6168fSJeff Roberson  * Return some of the child's priority and interactivity to the parent.
158635e6168fSJeff Roberson  */
158735e6168fSJeff Roberson void
1588ed062c8dSJulian Elischer sched_exit(struct proc *p, struct thread *childtd)
158935e6168fSJeff Roberson {
159035e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
1591ed062c8dSJulian Elischer 	sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), childtd);
159281d47d3fSJeff Roberson 	sched_exit_thread(NULL, childtd);
1593141ad61cSJeff Roberson }
1594141ad61cSJeff Roberson 
1595141ad61cSJeff Roberson void
159655d44f79SJulian Elischer sched_exit_ksegrp(struct ksegrp *kg, struct thread *td)
1597141ad61cSJeff Roberson {
159855d44f79SJulian Elischer 	/* kg->kg_slptime += td->td_ksegrp->kg_slptime; */
159955d44f79SJulian Elischer 	kg->kg_runtime += td->td_ksegrp->kg_runtime;
16004b60e324SJeff Roberson 	sched_interact_update(kg);
1601141ad61cSJeff Roberson }
1602141ad61cSJeff Roberson 
1603141ad61cSJeff Roberson void
1604ed062c8dSJulian Elischer sched_exit_thread(struct thread *td, struct thread *childtd)
1605141ad61cSJeff Roberson {
160681d47d3fSJeff Roberson 	CTR3(KTR_SCHED, "sched_exit_thread: %p(%s) prio %d",
160781d47d3fSJeff Roberson 	    childtd, childtd->td_proc->p_comm, childtd->td_priority);
1608ed062c8dSJulian Elischer 	kseq_load_rem(KSEQ_CPU(childtd->td_kse->ke_cpu), childtd->td_kse);
160935e6168fSJeff Roberson }
161035e6168fSJeff Roberson 
161135e6168fSJeff Roberson void
16127cf90fb3SJeff Roberson sched_clock(struct thread *td)
161335e6168fSJeff Roberson {
161435e6168fSJeff Roberson 	struct kseq *kseq;
16150a016a05SJeff Roberson 	struct ksegrp *kg;
16167cf90fb3SJeff Roberson 	struct kse *ke;
161735e6168fSJeff Roberson 
1618dc03363dSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
16192454aaf5SJeff Roberson 	kseq = KSEQ_SELF();
1620dc03363dSJeff Roberson #ifdef SMP
1621598b368dSJeff Roberson 	if (ticks >= bal_tick)
1622dc03363dSJeff Roberson 		sched_balance();
1623598b368dSJeff Roberson 	if (ticks >= gbal_tick && balance_groups)
1624dc03363dSJeff Roberson 		sched_balance_groups();
16252454aaf5SJeff Roberson 	/*
16262454aaf5SJeff Roberson 	 * We could have been assigned a non real-time thread without an
16272454aaf5SJeff Roberson 	 * IPI.
16282454aaf5SJeff Roberson 	 */
16292454aaf5SJeff Roberson 	if (kseq->ksq_assigned)
16302454aaf5SJeff Roberson 		kseq_assign(kseq);	/* Potentially sets NEEDRESCHED */
1631dc03363dSJeff Roberson #endif
163215dc847eSJeff Roberson 	/*
163315dc847eSJeff Roberson 	 * sched_setup() apparently happens prior to stathz being set.  We
163415dc847eSJeff Roberson 	 * need to resolve the timers earlier in the boot so we can avoid
163515dc847eSJeff Roberson 	 * calculating this here.
163615dc847eSJeff Roberson 	 */
163715dc847eSJeff Roberson 	if (realstathz == 0) {
163815dc847eSJeff Roberson 		realstathz = stathz ? stathz : hz;
163915dc847eSJeff Roberson 		tickincr = hz / realstathz;
164015dc847eSJeff Roberson 		/*
164115dc847eSJeff Roberson 		 * XXX This does not work for values of stathz that are much
164215dc847eSJeff Roberson 		 * larger than hz.
164315dc847eSJeff Roberson 		 */
164415dc847eSJeff Roberson 		if (tickincr == 0)
164515dc847eSJeff Roberson 			tickincr = 1;
164615dc847eSJeff Roberson 	}
164735e6168fSJeff Roberson 
16487cf90fb3SJeff Roberson 	ke = td->td_kse;
164915dc847eSJeff Roberson 	kg = ke->ke_ksegrp;
165035e6168fSJeff Roberson 
16510a016a05SJeff Roberson 	/* Adjust ticks for pctcpu */
165265c8760dSJeff Roberson 	ke->ke_ticks++;
1653d465fb95SJeff Roberson 	ke->ke_ltick = ticks;
1654a8949de2SJeff Roberson 
1655d465fb95SJeff Roberson 	/* Go up to one second beyond our max and then trim back down */
1656d465fb95SJeff Roberson 	if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick)
1657d465fb95SJeff Roberson 		sched_pctcpu_update(ke);
1658d465fb95SJeff Roberson 
165943fdafb1SJulian Elischer 	if (td->td_flags & TDF_IDLETD)
166035e6168fSJeff Roberson 		return;
16613f741ca1SJeff Roberson 	/*
1662a8949de2SJeff Roberson 	 * We only do slicing code for TIMESHARE ksegrps.
1663a8949de2SJeff Roberson 	 */
1664a8949de2SJeff Roberson 	if (kg->kg_pri_class != PRI_TIMESHARE)
1665a8949de2SJeff Roberson 		return;
1666a8949de2SJeff Roberson 	/*
166715dc847eSJeff Roberson 	 * We used a tick charge it to the ksegrp so that we can compute our
166815dc847eSJeff Roberson 	 * interactivity.
166915dc847eSJeff Roberson 	 */
167015dc847eSJeff Roberson 	kg->kg_runtime += tickincr << 10;
16714b60e324SJeff Roberson 	sched_interact_update(kg);
1672407b0157SJeff Roberson 
167335e6168fSJeff Roberson 	/*
167435e6168fSJeff Roberson 	 * We used up one time slice.
167535e6168fSJeff Roberson 	 */
1676093c05e3SJeff Roberson 	if (--ke->ke_slice > 0)
167715dc847eSJeff Roberson 		return;
167835e6168fSJeff Roberson 	/*
167915dc847eSJeff Roberson 	 * We're out of time, recompute priorities and requeue.
168035e6168fSJeff Roberson 	 */
1681155b9987SJeff Roberson 	kseq_load_rem(kseq, ke);
1682e1f89c22SJeff Roberson 	sched_priority(kg);
168315dc847eSJeff Roberson 	sched_slice(ke);
168415dc847eSJeff Roberson 	if (SCHED_CURR(kg, ke))
168515dc847eSJeff Roberson 		ke->ke_runq = kseq->ksq_curr;
168615dc847eSJeff Roberson 	else
168715dc847eSJeff Roberson 		ke->ke_runq = kseq->ksq_next;
1688155b9987SJeff Roberson 	kseq_load_add(kseq, ke);
16894a338afdSJulian Elischer 	td->td_flags |= TDF_NEEDRESCHED;
169035e6168fSJeff Roberson }
169135e6168fSJeff Roberson 
169235e6168fSJeff Roberson int
169335e6168fSJeff Roberson sched_runnable(void)
169435e6168fSJeff Roberson {
169535e6168fSJeff Roberson 	struct kseq *kseq;
1696b90816f1SJeff Roberson 	int load;
169735e6168fSJeff Roberson 
1698b90816f1SJeff Roberson 	load = 1;
1699b90816f1SJeff Roberson 
17000a016a05SJeff Roberson 	kseq = KSEQ_SELF();
170122bf7d9aSJeff Roberson #ifdef SMP
170246f8b265SJeff Roberson 	if (kseq->ksq_assigned) {
170346f8b265SJeff Roberson 		mtx_lock_spin(&sched_lock);
170422bf7d9aSJeff Roberson 		kseq_assign(kseq);
170546f8b265SJeff Roberson 		mtx_unlock_spin(&sched_lock);
170646f8b265SJeff Roberson 	}
170722bf7d9aSJeff Roberson #endif
17083f741ca1SJeff Roberson 	if ((curthread->td_flags & TDF_IDLETD) != 0) {
17093f741ca1SJeff Roberson 		if (kseq->ksq_load > 0)
17103f741ca1SJeff Roberson 			goto out;
17113f741ca1SJeff Roberson 	} else
17123f741ca1SJeff Roberson 		if (kseq->ksq_load - 1 > 0)
1713b90816f1SJeff Roberson 			goto out;
1714b90816f1SJeff Roberson 	load = 0;
1715b90816f1SJeff Roberson out:
1716b90816f1SJeff Roberson 	return (load);
171735e6168fSJeff Roberson }
171835e6168fSJeff Roberson 
171935e6168fSJeff Roberson void
172035e6168fSJeff Roberson sched_userret(struct thread *td)
172135e6168fSJeff Roberson {
172235e6168fSJeff Roberson 	struct ksegrp *kg;
172335e6168fSJeff Roberson 
1724f5c157d9SJohn Baldwin 	KASSERT((td->td_flags & TDF_BORROWING) == 0,
1725f5c157d9SJohn Baldwin 	    ("thread with borrowed priority returning to userland"));
172635e6168fSJeff Roberson 	kg = td->td_ksegrp;
1727f5c157d9SJohn Baldwin 	if (td->td_priority != kg->kg_user_pri) {
172835e6168fSJeff Roberson 		mtx_lock_spin(&sched_lock);
172935e6168fSJeff Roberson 		td->td_priority = kg->kg_user_pri;
1730f5c157d9SJohn Baldwin 		td->td_base_pri = kg->kg_user_pri;
173135e6168fSJeff Roberson 		mtx_unlock_spin(&sched_lock);
173235e6168fSJeff Roberson 	}
173335e6168fSJeff Roberson }
173435e6168fSJeff Roberson 
1735c9f25d8fSJeff Roberson struct kse *
1736c9f25d8fSJeff Roberson sched_choose(void)
1737c9f25d8fSJeff Roberson {
17380a016a05SJeff Roberson 	struct kseq *kseq;
1739c9f25d8fSJeff Roberson 	struct kse *ke;
174015dc847eSJeff Roberson 
1741b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
174222bf7d9aSJeff Roberson 	kseq = KSEQ_SELF();
174315dc847eSJeff Roberson #ifdef SMP
174480f86c9fSJeff Roberson restart:
174522bf7d9aSJeff Roberson 	if (kseq->ksq_assigned)
174622bf7d9aSJeff Roberson 		kseq_assign(kseq);
174715dc847eSJeff Roberson #endif
174822bf7d9aSJeff Roberson 	ke = kseq_choose(kseq);
174935e6168fSJeff Roberson 	if (ke) {
175022bf7d9aSJeff Roberson #ifdef SMP
175122bf7d9aSJeff Roberson 		if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE)
175280f86c9fSJeff Roberson 			if (kseq_idled(kseq) == 0)
175380f86c9fSJeff Roberson 				goto restart;
175422bf7d9aSJeff Roberson #endif
1755155b9987SJeff Roberson 		kseq_runq_rem(kseq, ke);
175635e6168fSJeff Roberson 		ke->ke_state = KES_THREAD;
175715dc847eSJeff Roberson 		return (ke);
175835e6168fSJeff Roberson 	}
1759c9f25d8fSJeff Roberson #ifdef SMP
176080f86c9fSJeff Roberson 	if (kseq_idled(kseq) == 0)
176180f86c9fSJeff Roberson 		goto restart;
1762c9f25d8fSJeff Roberson #endif
176315dc847eSJeff Roberson 	return (NULL);
176435e6168fSJeff Roberson }
176535e6168fSJeff Roberson 
176635e6168fSJeff Roberson void
17672630e4c9SJulian Elischer sched_add(struct thread *td, int flags)
176835e6168fSJeff Roberson {
1769c9f25d8fSJeff Roberson 	struct kseq *kseq;
177015dc847eSJeff Roberson 	struct ksegrp *kg;
17717cf90fb3SJeff Roberson 	struct kse *ke;
1772598b368dSJeff Roberson 	int preemptive;
17732454aaf5SJeff Roberson 	int canmigrate;
177422bf7d9aSJeff Roberson 	int class;
1775c9f25d8fSJeff Roberson 
177681d47d3fSJeff Roberson 	CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)",
177781d47d3fSJeff Roberson 	    td, td->td_proc->p_comm, td->td_priority, curthread,
177881d47d3fSJeff Roberson 	    curthread->td_proc->p_comm);
177922bf7d9aSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
17807cf90fb3SJeff Roberson 	ke = td->td_kse;
17817cf90fb3SJeff Roberson 	kg = td->td_ksegrp;
1782598b368dSJeff Roberson 	canmigrate = 1;
1783598b368dSJeff Roberson 	preemptive = !(flags & SRQ_YIELDING);
1784598b368dSJeff Roberson 	class = PRI_BASE(kg->kg_pri_class);
1785598b368dSJeff Roberson 	kseq = KSEQ_SELF();
1786598b368dSJeff Roberson 	if ((ke->ke_flags & KEF_INTERNAL) == 0)
1787598b368dSJeff Roberson 		SLOT_USE(td->td_ksegrp);
1788598b368dSJeff Roberson 	ke->ke_flags &= ~KEF_INTERNAL;
1789598b368dSJeff Roberson #ifdef SMP
17902d59a44dSJeff Roberson 	if (ke->ke_flags & KEF_ASSIGNED) {
1791598b368dSJeff Roberson 		if (ke->ke_flags & KEF_REMOVED)
17922d59a44dSJeff Roberson 			ke->ke_flags &= ~KEF_REMOVED;
179322bf7d9aSJeff Roberson 		return;
17942d59a44dSJeff Roberson 	}
1795598b368dSJeff Roberson 	canmigrate = KSE_CAN_MIGRATE(ke);
1796598b368dSJeff Roberson #endif
17975d7ef00cSJeff Roberson 	KASSERT(ke->ke_state != KES_ONRUNQ,
17985d7ef00cSJeff Roberson 	    ("sched_add: kse %p (%s) already in run queue", ke,
17995d7ef00cSJeff Roberson 	    ke->ke_proc->p_comm));
18005d7ef00cSJeff Roberson 	KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
18015d7ef00cSJeff Roberson 	    ("sched_add: process swapped out"));
18029bca28a7SJeff Roberson 	KASSERT(ke->ke_runq == NULL,
18039bca28a7SJeff Roberson 	    ("sched_add: KSE %p is still assigned to a run queue", ke));
180422bf7d9aSJeff Roberson 	switch (class) {
1805a8949de2SJeff Roberson 	case PRI_ITHD:
1806a8949de2SJeff Roberson 	case PRI_REALTIME:
180715dc847eSJeff Roberson 		ke->ke_runq = kseq->ksq_curr;
180815dc847eSJeff Roberson 		ke->ke_slice = SCHED_SLICE_MAX;
1809598b368dSJeff Roberson 		if (canmigrate)
18107cd650a9SJeff Roberson 			ke->ke_cpu = PCPU_GET(cpuid);
1811a8949de2SJeff Roberson 		break;
1812a8949de2SJeff Roberson 	case PRI_TIMESHARE:
181315dc847eSJeff Roberson 		if (SCHED_CURR(kg, ke))
181415dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_curr;
181515dc847eSJeff Roberson 		else
181615dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_next;
181715dc847eSJeff Roberson 		break;
181815dc847eSJeff Roberson 	case PRI_IDLE:
181915dc847eSJeff Roberson 		/*
182015dc847eSJeff Roberson 		 * This is for priority prop.
182115dc847eSJeff Roberson 		 */
18223f741ca1SJeff Roberson 		if (ke->ke_thread->td_priority < PRI_MIN_IDLE)
182315dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_curr;
182415dc847eSJeff Roberson 		else
182515dc847eSJeff Roberson 			ke->ke_runq = &kseq->ksq_idle;
182615dc847eSJeff Roberson 		ke->ke_slice = SCHED_SLICE_MIN;
182715dc847eSJeff Roberson 		break;
182815dc847eSJeff Roberson 	default:
1829d322132cSJeff Roberson 		panic("Unknown pri class.");
1830a8949de2SJeff Roberson 		break;
1831a6ed4186SJeff Roberson 	}
183222bf7d9aSJeff Roberson #ifdef SMP
18332454aaf5SJeff Roberson 	/*
18342454aaf5SJeff Roberson 	 * Don't migrate running threads here.  Force the long term balancer
18352454aaf5SJeff Roberson 	 * to do it.
18362454aaf5SJeff Roberson 	 */
1837f2b74cbfSJeff Roberson 	if (ke->ke_flags & KEF_HOLD) {
1838f2b74cbfSJeff Roberson 		ke->ke_flags &= ~KEF_HOLD;
18392454aaf5SJeff Roberson 		canmigrate = 0;
1840f2b74cbfSJeff Roberson 	}
18412454aaf5SJeff Roberson 	/*
18422454aaf5SJeff Roberson 	 * If this thread is pinned or bound, notify the target cpu.
18432454aaf5SJeff Roberson 	 */
18442454aaf5SJeff Roberson 	if (!canmigrate && ke->ke_cpu != PCPU_GET(cpuid) ) {
184586e1c22aSJeff Roberson 		ke->ke_runq = NULL;
184680f86c9fSJeff Roberson 		kseq_notify(ke, ke->ke_cpu);
184780f86c9fSJeff Roberson 		return;
184880f86c9fSJeff Roberson 	}
184922bf7d9aSJeff Roberson 	/*
1850670c524fSJeff Roberson 	 * If we had been idle, clear our bit in the group and potentially
1851670c524fSJeff Roberson 	 * the global bitmap.  If not, see if we should transfer this thread.
185222bf7d9aSJeff Roberson 	 */
185380f86c9fSJeff Roberson 	if ((class == PRI_TIMESHARE || class == PRI_REALTIME) &&
185480f86c9fSJeff Roberson 	    (kseq->ksq_group->ksg_idlemask & PCPU_GET(cpumask)) != 0) {
185580f86c9fSJeff Roberson 		/*
185680f86c9fSJeff Roberson 		 * Check to see if our group is unidling, and if so, remove it
185780f86c9fSJeff Roberson 		 * from the global idle mask.
185880f86c9fSJeff Roberson 		 */
185980f86c9fSJeff Roberson 		if (kseq->ksq_group->ksg_idlemask ==
186080f86c9fSJeff Roberson 		    kseq->ksq_group->ksg_cpumask)
186180f86c9fSJeff Roberson 			atomic_clear_int(&kseq_idle, kseq->ksq_group->ksg_mask);
186280f86c9fSJeff Roberson 		/*
186380f86c9fSJeff Roberson 		 * Now remove ourselves from the group specific idle mask.
186480f86c9fSJeff Roberson 		 */
186580f86c9fSJeff Roberson 		kseq->ksq_group->ksg_idlemask &= ~PCPU_GET(cpumask);
1866598b368dSJeff Roberson 	} else if (canmigrate && kseq->ksq_load > 1 && class != PRI_ITHD)
1867670c524fSJeff Roberson 		if (kseq_transfer(kseq, ke, class))
1868670c524fSJeff Roberson 			return;
18692454aaf5SJeff Roberson 	ke->ke_cpu = PCPU_GET(cpuid);
187022bf7d9aSJeff Roberson #endif
1871f2b74cbfSJeff Roberson 	if (td->td_priority < curthread->td_priority &&
1872f2b74cbfSJeff Roberson 	    ke->ke_runq == kseq->ksq_curr)
187322bf7d9aSJeff Roberson 		curthread->td_flags |= TDF_NEEDRESCHED;
187463fcce68SJohn Baldwin 	if (preemptive && maybe_preempt(td))
18750c0b25aeSJohn Baldwin 		return;
187635e6168fSJeff Roberson 	ke->ke_state = KES_ONRUNQ;
187735e6168fSJeff Roberson 
1878598b368dSJeff Roberson 	kseq_runq_add(kseq, ke, flags);
1879155b9987SJeff Roberson 	kseq_load_add(kseq, ke);
188035e6168fSJeff Roberson }
188135e6168fSJeff Roberson 
188235e6168fSJeff Roberson void
18837cf90fb3SJeff Roberson sched_rem(struct thread *td)
188435e6168fSJeff Roberson {
188515dc847eSJeff Roberson 	struct kseq *kseq;
18867cf90fb3SJeff Roberson 	struct kse *ke;
18877cf90fb3SJeff Roberson 
188881d47d3fSJeff Roberson 	CTR5(KTR_SCHED, "sched_rem: %p(%s) prio %d by %p(%s)",
188981d47d3fSJeff Roberson 	    td, td->td_proc->p_comm, td->td_priority, curthread,
189081d47d3fSJeff Roberson 	    curthread->td_proc->p_comm);
1891598b368dSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
1892598b368dSJeff Roberson 	ke = td->td_kse;
18932d59a44dSJeff Roberson 	SLOT_RELEASE(td->td_ksegrp);
1894598b368dSJeff Roberson 	if (ke->ke_flags & KEF_ASSIGNED) {
18952d59a44dSJeff Roberson 		ke->ke_flags |= KEF_REMOVED;
189622bf7d9aSJeff Roberson 		return;
18972d59a44dSJeff Roberson 	}
1898c494ddc8SJeff Roberson 	KASSERT((ke->ke_state == KES_ONRUNQ),
1899c494ddc8SJeff Roberson 	    ("sched_rem: KSE not on run queue"));
190035e6168fSJeff Roberson 
19012d59a44dSJeff Roberson 	ke->ke_state = KES_THREAD;
190215dc847eSJeff Roberson 	kseq = KSEQ_CPU(ke->ke_cpu);
1903155b9987SJeff Roberson 	kseq_runq_rem(kseq, ke);
1904155b9987SJeff Roberson 	kseq_load_rem(kseq, ke);
190535e6168fSJeff Roberson }
190635e6168fSJeff Roberson 
190735e6168fSJeff Roberson fixpt_t
19087cf90fb3SJeff Roberson sched_pctcpu(struct thread *td)
190935e6168fSJeff Roberson {
191035e6168fSJeff Roberson 	fixpt_t pctcpu;
19117cf90fb3SJeff Roberson 	struct kse *ke;
191235e6168fSJeff Roberson 
191335e6168fSJeff Roberson 	pctcpu = 0;
19147cf90fb3SJeff Roberson 	ke = td->td_kse;
1915484288deSJeff Roberson 	if (ke == NULL)
1916484288deSJeff Roberson 		return (0);
191735e6168fSJeff Roberson 
1918b90816f1SJeff Roberson 	mtx_lock_spin(&sched_lock);
191935e6168fSJeff Roberson 	if (ke->ke_ticks) {
192035e6168fSJeff Roberson 		int rtick;
192135e6168fSJeff Roberson 
1922210491d3SJeff Roberson 		/*
1923210491d3SJeff Roberson 		 * Don't update more frequently than twice a second.  Allowing
1924210491d3SJeff Roberson 		 * this causes the cpu usage to decay away too quickly due to
1925210491d3SJeff Roberson 		 * rounding errors.
1926210491d3SJeff Roberson 		 */
19272e227f04SJeff Roberson 		if (ke->ke_ftick + SCHED_CPU_TICKS < ke->ke_ltick ||
19282e227f04SJeff Roberson 		    ke->ke_ltick < (ticks - (hz / 2)))
192935e6168fSJeff Roberson 			sched_pctcpu_update(ke);
193035e6168fSJeff Roberson 		/* How many rtick per second ? */
1931210491d3SJeff Roberson 		rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS);
19327121cce5SScott Long 		pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT;
193335e6168fSJeff Roberson 	}
193435e6168fSJeff Roberson 
193535e6168fSJeff Roberson 	ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick;
1936828e7683SJohn Baldwin 	mtx_unlock_spin(&sched_lock);
193735e6168fSJeff Roberson 
193835e6168fSJeff Roberson 	return (pctcpu);
193935e6168fSJeff Roberson }
194035e6168fSJeff Roberson 
19419bacd788SJeff Roberson void
19429bacd788SJeff Roberson sched_bind(struct thread *td, int cpu)
19439bacd788SJeff Roberson {
19449bacd788SJeff Roberson 	struct kse *ke;
19459bacd788SJeff Roberson 
19469bacd788SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
19479bacd788SJeff Roberson 	ke = td->td_kse;
19489bacd788SJeff Roberson 	ke->ke_flags |= KEF_BOUND;
194980f86c9fSJeff Roberson #ifdef SMP
195080f86c9fSJeff Roberson 	if (PCPU_GET(cpuid) == cpu)
19519bacd788SJeff Roberson 		return;
19529bacd788SJeff Roberson 	/* sched_rem without the runq_remove */
19539bacd788SJeff Roberson 	ke->ke_state = KES_THREAD;
1954155b9987SJeff Roberson 	kseq_load_rem(KSEQ_CPU(ke->ke_cpu), ke);
19559bacd788SJeff Roberson 	kseq_notify(ke, cpu);
19569bacd788SJeff Roberson 	/* When we return from mi_switch we'll be on the correct cpu. */
1957279f949eSPoul-Henning Kamp 	mi_switch(SW_VOL, NULL);
19589bacd788SJeff Roberson #endif
19599bacd788SJeff Roberson }
19609bacd788SJeff Roberson 
19619bacd788SJeff Roberson void
19629bacd788SJeff Roberson sched_unbind(struct thread *td)
19639bacd788SJeff Roberson {
19649bacd788SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
19659bacd788SJeff Roberson 	td->td_kse->ke_flags &= ~KEF_BOUND;
19669bacd788SJeff Roberson }
19679bacd788SJeff Roberson 
196835e6168fSJeff Roberson int
1969ebccf1e3SJoseph Koshy sched_is_bound(struct thread *td)
1970ebccf1e3SJoseph Koshy {
1971ebccf1e3SJoseph Koshy 	mtx_assert(&sched_lock, MA_OWNED);
1972ebccf1e3SJoseph Koshy 	return (td->td_kse->ke_flags & KEF_BOUND);
1973ebccf1e3SJoseph Koshy }
1974ebccf1e3SJoseph Koshy 
1975ebccf1e3SJoseph Koshy int
197633916c36SJeff Roberson sched_load(void)
197733916c36SJeff Roberson {
197833916c36SJeff Roberson #ifdef SMP
197933916c36SJeff Roberson 	int total;
198033916c36SJeff Roberson 	int i;
198133916c36SJeff Roberson 
198233916c36SJeff Roberson 	total = 0;
198333916c36SJeff Roberson 	for (i = 0; i <= ksg_maxid; i++)
198433916c36SJeff Roberson 		total += KSEQ_GROUP(i)->ksg_load;
198533916c36SJeff Roberson 	return (total);
198633916c36SJeff Roberson #else
198733916c36SJeff Roberson 	return (KSEQ_SELF()->ksq_sysload);
198833916c36SJeff Roberson #endif
198933916c36SJeff Roberson }
199033916c36SJeff Roberson 
199133916c36SJeff Roberson int
199235e6168fSJeff Roberson sched_sizeof_ksegrp(void)
199335e6168fSJeff Roberson {
199435e6168fSJeff Roberson 	return (sizeof(struct ksegrp) + sizeof(struct kg_sched));
199535e6168fSJeff Roberson }
199635e6168fSJeff Roberson 
199735e6168fSJeff Roberson int
199835e6168fSJeff Roberson sched_sizeof_proc(void)
199935e6168fSJeff Roberson {
200035e6168fSJeff Roberson 	return (sizeof(struct proc));
200135e6168fSJeff Roberson }
200235e6168fSJeff Roberson 
200335e6168fSJeff Roberson int
200435e6168fSJeff Roberson sched_sizeof_thread(void)
200535e6168fSJeff Roberson {
200635e6168fSJeff Roberson 	return (sizeof(struct thread) + sizeof(struct td_sched));
200735e6168fSJeff Roberson }
2008ed062c8dSJulian Elischer #define KERN_SWITCH_INCLUDE 1
2009ed062c8dSJulian Elischer #include "kern/kern_switch.c"
2010