xref: /freebsd/sys/kern/sched_ule.c (revision ae7a6b38d53f75f54d7f042053297070284c9ccf)
135e6168fSJeff Roberson /*-
2e7d50326SJeff Roberson  * Copyright (c) 2002-2007, 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 
27ae7a6b38SJeff Roberson /*
28ae7a6b38SJeff Roberson  * This file implements the ULE scheduler.  ULE supports independent CPU
29ae7a6b38SJeff Roberson  * run queues and fine grain locking.  It has superior interactive
30ae7a6b38SJeff Roberson  * performance under load even on uni-processor systems.
31ae7a6b38SJeff Roberson  *
32ae7a6b38SJeff Roberson  * etymology:
33ae7a6b38SJeff Roberson  *   ULE is the last three letters in schedule.  It owes it's name to a
34ae7a6b38SJeff Roberson  * generic user created for a scheduling system by Paul Mikesell at
35ae7a6b38SJeff Roberson  * Isilon Systems and a general lack of creativity on the part of the author.
36ae7a6b38SJeff Roberson  */
37ae7a6b38SJeff Roberson 
38677b542eSDavid E. O'Brien #include <sys/cdefs.h>
39677b542eSDavid E. O'Brien __FBSDID("$FreeBSD$");
40677b542eSDavid E. O'Brien 
414da0d332SPeter Wemm #include "opt_hwpmc_hooks.h"
424da0d332SPeter Wemm #include "opt_sched.h"
439923b511SScott Long 
4435e6168fSJeff Roberson #include <sys/param.h>
4535e6168fSJeff Roberson #include <sys/systm.h>
462c3490b1SMarcel Moolenaar #include <sys/kdb.h>
4735e6168fSJeff Roberson #include <sys/kernel.h>
4835e6168fSJeff Roberson #include <sys/ktr.h>
4935e6168fSJeff Roberson #include <sys/lock.h>
5035e6168fSJeff Roberson #include <sys/mutex.h>
5135e6168fSJeff Roberson #include <sys/proc.h>
52245f3abfSJeff Roberson #include <sys/resource.h>
539bacd788SJeff Roberson #include <sys/resourcevar.h>
5435e6168fSJeff Roberson #include <sys/sched.h>
5535e6168fSJeff Roberson #include <sys/smp.h>
5635e6168fSJeff Roberson #include <sys/sx.h>
5735e6168fSJeff Roberson #include <sys/sysctl.h>
5835e6168fSJeff Roberson #include <sys/sysproto.h>
59f5c157d9SJohn Baldwin #include <sys/turnstile.h>
603db720fdSDavid Xu #include <sys/umtx.h>
6135e6168fSJeff Roberson #include <sys/vmmeter.h>
6235e6168fSJeff Roberson #ifdef KTRACE
6335e6168fSJeff Roberson #include <sys/uio.h>
6435e6168fSJeff Roberson #include <sys/ktrace.h>
6535e6168fSJeff Roberson #endif
6635e6168fSJeff Roberson 
67ebccf1e3SJoseph Koshy #ifdef HWPMC_HOOKS
68ebccf1e3SJoseph Koshy #include <sys/pmckern.h>
69ebccf1e3SJoseph Koshy #endif
70ebccf1e3SJoseph Koshy 
7135e6168fSJeff Roberson #include <machine/cpu.h>
7222bf7d9aSJeff Roberson #include <machine/smp.h>
7335e6168fSJeff Roberson 
747a5e5e2aSJeff Roberson #ifndef PREEMPTION
757a5e5e2aSJeff Roberson #error	"SCHED_ULE requires options PREEMPTION"
767a5e5e2aSJeff Roberson #endif
777a5e5e2aSJeff Roberson 
78ae7a6b38SJeff Roberson #define	KTR_ULE	0
7914618990SJeff Roberson 
806b2f763fSJeff Roberson /*
81ae7a6b38SJeff Roberson  * Thread scheduler specific section.  All fields are protected
82ae7a6b38SJeff Roberson  * by the thread lock.
83ed062c8dSJulian Elischer  */
84ad1e7d28SJulian Elischer struct td_sched {
85ae7a6b38SJeff Roberson 	TAILQ_ENTRY(td_sched) ts_procq;	/* Run queue. */
86ae7a6b38SJeff Roberson 	struct thread	*ts_thread;	/* Active associated thread. */
87ae7a6b38SJeff Roberson 	struct runq	*ts_runq;	/* Run-queue we're queued on. */
88ae7a6b38SJeff Roberson 	short		ts_flags;	/* TSF_* flags. */
89ae7a6b38SJeff Roberson 	u_char		ts_rqindex;	/* Run queue index. */
90ad1e7d28SJulian Elischer 	u_char		ts_cpu;		/* CPU that we have affinity for. */
91ae7a6b38SJeff Roberson 	int		ts_slptick;	/* Tick when we went to sleep. */
92ae7a6b38SJeff Roberson 	int		ts_slice;	/* Ticks of slice remaining. */
93ae7a6b38SJeff Roberson 	u_int		ts_slptime;	/* Number of ticks we vol. slept */
94ae7a6b38SJeff Roberson 	u_int		ts_runtime;	/* Number of ticks we were running */
95ed062c8dSJulian Elischer 	/* The following variables are only used for pctcpu calculation */
96ad1e7d28SJulian Elischer 	int		ts_ltick;	/* Last tick that we were running on */
97ad1e7d28SJulian Elischer 	int		ts_ftick;	/* First tick that we were running on */
98ad1e7d28SJulian Elischer 	int		ts_ticks;	/* Tick count */
997b8bfa0dSJeff Roberson #ifdef SMP
1007b8bfa0dSJeff Roberson 	int		ts_rltick;	/* Real last tick, for affinity. */
1017b8bfa0dSJeff Roberson #endif
102ed062c8dSJulian Elischer };
103ad1e7d28SJulian Elischer /* flags kept in ts_flags */
1047b8bfa0dSJeff Roberson #define	TSF_BOUND	0x0001		/* Thread can not migrate. */
1057b8bfa0dSJeff Roberson #define	TSF_XFERABLE	0x0002		/* Thread was added as transferable. */
10635e6168fSJeff Roberson 
107ad1e7d28SJulian Elischer static struct td_sched td_sched0;
10835e6168fSJeff Roberson 
10935e6168fSJeff Roberson /*
110e7d50326SJeff Roberson  * Cpu percentage computation macros and defines.
111e1f89c22SJeff Roberson  *
112e7d50326SJeff Roberson  * SCHED_TICK_SECS:	Number of seconds to average the cpu usage across.
113e7d50326SJeff Roberson  * SCHED_TICK_TARG:	Number of hz ticks to average the cpu usage across.
1148ab80cf0SJeff Roberson  * SCHED_TICK_MAX:	Maximum number of ticks before scaling back.
115e7d50326SJeff Roberson  * SCHED_TICK_SHIFT:	Shift factor to avoid rounding away results.
116e7d50326SJeff Roberson  * SCHED_TICK_HZ:	Compute the number of hz ticks for a given ticks count.
117e7d50326SJeff Roberson  * SCHED_TICK_TOTAL:	Gives the amount of time we've been recording ticks.
11835e6168fSJeff Roberson  */
119e7d50326SJeff Roberson #define	SCHED_TICK_SECS		10
120e7d50326SJeff Roberson #define	SCHED_TICK_TARG		(hz * SCHED_TICK_SECS)
1218ab80cf0SJeff Roberson #define	SCHED_TICK_MAX		(SCHED_TICK_TARG + hz)
122e7d50326SJeff Roberson #define	SCHED_TICK_SHIFT	10
123e7d50326SJeff Roberson #define	SCHED_TICK_HZ(ts)	((ts)->ts_ticks >> SCHED_TICK_SHIFT)
124eddb4efaSJeff Roberson #define	SCHED_TICK_TOTAL(ts)	(max((ts)->ts_ltick - (ts)->ts_ftick, hz))
12535e6168fSJeff Roberson 
12635e6168fSJeff Roberson /*
127e7d50326SJeff Roberson  * These macros determine priorities for non-interactive threads.  They are
128e7d50326SJeff Roberson  * assigned a priority based on their recent cpu utilization as expressed
129e7d50326SJeff Roberson  * by the ratio of ticks to the tick total.  NHALF priorities at the start
130e7d50326SJeff Roberson  * and end of the MIN to MAX timeshare range are only reachable with negative
131e7d50326SJeff Roberson  * or positive nice respectively.
132e7d50326SJeff Roberson  *
133e7d50326SJeff Roberson  * PRI_RANGE:	Priority range for utilization dependent priorities.
134e7d50326SJeff Roberson  * PRI_NRESV:	Number of nice values.
135e7d50326SJeff Roberson  * PRI_TICKS:	Compute a priority in PRI_RANGE from the ticks count and total.
136e7d50326SJeff Roberson  * PRI_NICE:	Determines the part of the priority inherited from nice.
137e7d50326SJeff Roberson  */
138e7d50326SJeff Roberson #define	SCHED_PRI_NRESV		(PRIO_MAX - PRIO_MIN)
139e7d50326SJeff Roberson #define	SCHED_PRI_NHALF		(SCHED_PRI_NRESV / 2)
140e7d50326SJeff Roberson #define	SCHED_PRI_MIN		(PRI_MIN_TIMESHARE + SCHED_PRI_NHALF)
141e7d50326SJeff Roberson #define	SCHED_PRI_MAX		(PRI_MAX_TIMESHARE - SCHED_PRI_NHALF)
142dda713dfSJeff Roberson #define	SCHED_PRI_RANGE		(SCHED_PRI_MAX - SCHED_PRI_MIN)
143e7d50326SJeff Roberson #define	SCHED_PRI_TICKS(ts)						\
144e7d50326SJeff Roberson     (SCHED_TICK_HZ((ts)) /						\
1451e516cf5SJeff Roberson     (roundup(SCHED_TICK_TOTAL((ts)), SCHED_PRI_RANGE) / SCHED_PRI_RANGE))
146e7d50326SJeff Roberson #define	SCHED_PRI_NICE(nice)	(nice)
147e7d50326SJeff Roberson 
148e7d50326SJeff Roberson /*
149e7d50326SJeff Roberson  * These determine the interactivity of a process.  Interactivity differs from
150e7d50326SJeff Roberson  * cpu utilization in that it expresses the voluntary time slept vs time ran
151e7d50326SJeff Roberson  * while cpu utilization includes all time not running.  This more accurately
152e7d50326SJeff Roberson  * models the intent of the thread.
15335e6168fSJeff Roberson  *
154407b0157SJeff Roberson  * SLP_RUN_MAX:	Maximum amount of sleep time + run time we'll accumulate
155407b0157SJeff Roberson  *		before throttling back.
156d322132cSJeff Roberson  * SLP_RUN_FORK:	Maximum slp+run time to inherit at fork time.
157210491d3SJeff Roberson  * INTERACT_MAX:	Maximum interactivity value.  Smaller is better.
158e1f89c22SJeff Roberson  * INTERACT_THRESH:	Threshhold for placement on the current runq.
15935e6168fSJeff Roberson  */
160e7d50326SJeff Roberson #define	SCHED_SLP_RUN_MAX	((hz * 5) << SCHED_TICK_SHIFT)
161e7d50326SJeff Roberson #define	SCHED_SLP_RUN_FORK	((hz / 2) << SCHED_TICK_SHIFT)
162210491d3SJeff Roberson #define	SCHED_INTERACT_MAX	(100)
163210491d3SJeff Roberson #define	SCHED_INTERACT_HALF	(SCHED_INTERACT_MAX / 2)
1644c9612c6SJeff Roberson #define	SCHED_INTERACT_THRESH	(30)
165e1f89c22SJeff Roberson 
16635e6168fSJeff Roberson /*
167e7d50326SJeff Roberson  * tickincr:		Converts a stathz tick into a hz domain scaled by
168e7d50326SJeff Roberson  *			the shift factor.  Without the shift the error rate
169e7d50326SJeff Roberson  *			due to rounding would be unacceptably high.
170e7d50326SJeff Roberson  * realstathz:		stathz is sometimes 0 and run off of hz.
171e7d50326SJeff Roberson  * sched_slice:		Runtime of each thread before rescheduling.
172ae7a6b38SJeff Roberson  * preempt_thresh:	Priority threshold for preemption and remote IPIs.
17335e6168fSJeff Roberson  */
174e7d50326SJeff Roberson static int sched_interact = SCHED_INTERACT_THRESH;
175e7d50326SJeff Roberson static int realstathz;
176e7d50326SJeff Roberson static int tickincr;
177e7d50326SJeff Roberson static int sched_slice;
178ae7a6b38SJeff Roberson static int preempt_thresh = PRI_MIN_KERN;
179ae7a6b38SJeff Roberson 
180ae7a6b38SJeff Roberson #define	SCHED_BAL_SECS	2	/* How often we run the rebalance algorithm. */
18135e6168fSJeff Roberson 
18235e6168fSJeff Roberson /*
183ae7a6b38SJeff Roberson  * tdq - per processor runqs and statistics.  All fields are protected by the
184ae7a6b38SJeff Roberson  * tdq_lock.  The load and lowpri may be accessed without to avoid excess
185ae7a6b38SJeff Roberson  * locking in sched_pickcpu();
18635e6168fSJeff Roberson  */
187ad1e7d28SJulian Elischer struct tdq {
188ae7a6b38SJeff Roberson 	struct mtx	tdq_lock;		/* Protects all fields below. */
189e7d50326SJeff Roberson 	struct runq	tdq_realtime;		/* real-time run queue. */
190ae7a6b38SJeff Roberson 	struct runq	tdq_timeshare;		/* timeshare run queue. */
191ae7a6b38SJeff Roberson 	struct runq	tdq_idle;		/* Queue of IDLE threads. */
192ae7a6b38SJeff Roberson 	int		tdq_load;		/* Aggregate load. */
193ed0e8f2fSJeff Roberson 	u_char		tdq_idx;		/* Current insert index. */
194ed0e8f2fSJeff Roberson 	u_char		tdq_ridx;		/* Current removal index. */
1955d7ef00cSJeff Roberson #ifdef SMP
196ae7a6b38SJeff Roberson 	u_char		tdq_lowpri;		/* Lowest priority thread. */
197ae7a6b38SJeff Roberson 	int		tdq_transferable;	/* Transferable thread count. */
198d2ad694cSJeff Roberson 	LIST_ENTRY(tdq)	tdq_siblings;		/* Next in tdq group. */
199d2ad694cSJeff Roberson 	struct tdq_group *tdq_group;		/* Our processor group. */
20033916c36SJeff Roberson #else
201d2ad694cSJeff Roberson 	int		tdq_sysload;		/* For loadavg, !ITHD load. */
2025d7ef00cSJeff Roberson #endif
203ae7a6b38SJeff Roberson 	char		tdq_name[16];		/* lock name. */
204ae7a6b38SJeff Roberson } __aligned(64);
20535e6168fSJeff Roberson 
2067b8bfa0dSJeff Roberson 
20780f86c9fSJeff Roberson #ifdef SMP
20880f86c9fSJeff Roberson /*
209ad1e7d28SJulian Elischer  * tdq groups are groups of processors which can cheaply share threads.  When
21080f86c9fSJeff Roberson  * one processor in the group goes idle it will check the runqs of the other
21180f86c9fSJeff Roberson  * processors in its group prior to halting and waiting for an interrupt.
21280f86c9fSJeff Roberson  * These groups are suitable for SMT (Symetric Multi-Threading) and not NUMA.
21380f86c9fSJeff Roberson  * In a numa environment we'd want an idle bitmap per group and a two tiered
21480f86c9fSJeff Roberson  * load balancer.
21580f86c9fSJeff Roberson  */
216ad1e7d28SJulian Elischer struct tdq_group {
217d2ad694cSJeff Roberson 	int	tdg_cpus;		/* Count of CPUs in this tdq group. */
218d2ad694cSJeff Roberson 	cpumask_t tdg_cpumask;		/* Mask of cpus in this group. */
219d2ad694cSJeff Roberson 	cpumask_t tdg_idlemask;		/* Idle cpus in this group. */
220d2ad694cSJeff Roberson 	cpumask_t tdg_mask;		/* Bit mask for first cpu. */
221d2ad694cSJeff Roberson 	int	tdg_load;		/* Total load of this group. */
222d2ad694cSJeff Roberson 	int	tdg_transferable;	/* Transferable load of this group. */
223d2ad694cSJeff Roberson 	LIST_HEAD(, tdq) tdg_members;	/* Linked list of all members. */
224ae7a6b38SJeff Roberson } __aligned(64);
2257b8bfa0dSJeff Roberson 
226ae7a6b38SJeff Roberson #define	SCHED_AFFINITY_DEFAULT	(max(1, hz / 300))
2277b8bfa0dSJeff Roberson #define	SCHED_AFFINITY(ts)	((ts)->ts_rltick > ticks - affinity)
2287b8bfa0dSJeff Roberson 
2297b8bfa0dSJeff Roberson /*
2307b8bfa0dSJeff Roberson  * Run-time tunables.
2317b8bfa0dSJeff Roberson  */
2325cea64d5SJeff Roberson static int rebalance = 0;
23336b36916SJeff Roberson static int pick_pri = 0;
234ae7a6b38SJeff Roberson static int pick_zero = 0;
2357b8bfa0dSJeff Roberson static int affinity;
2367b8bfa0dSJeff Roberson static int tryself = 1;
2377b8bfa0dSJeff Roberson static int tryselfidle = 1;
238ae7a6b38SJeff Roberson static int steal_htt = 0;
239ae7a6b38SJeff Roberson static int steal_idle = 0;
2407b20fb19SJeff Roberson static int topology = 0;
24180f86c9fSJeff Roberson 
24235e6168fSJeff Roberson /*
243d2ad694cSJeff Roberson  * One thread queue per processor.
24435e6168fSJeff Roberson  */
2457b8bfa0dSJeff Roberson static volatile cpumask_t tdq_idle;
246d2ad694cSJeff Roberson static int tdg_maxid;
247ad1e7d28SJulian Elischer static struct tdq	tdq_cpu[MAXCPU];
248ad1e7d28SJulian Elischer static struct tdq_group tdq_groups[MAXCPU];
249ae7a6b38SJeff Roberson static struct callout balco;
250ae7a6b38SJeff Roberson static struct callout gbalco;
251dc03363dSJeff Roberson 
252ad1e7d28SJulian Elischer #define	TDQ_SELF()	(&tdq_cpu[PCPU_GET(cpuid)])
253ad1e7d28SJulian Elischer #define	TDQ_CPU(x)	(&tdq_cpu[(x)])
254ad1e7d28SJulian Elischer #define	TDQ_ID(x)	((x) - tdq_cpu)
255ad1e7d28SJulian Elischer #define	TDQ_GROUP(x)	(&tdq_groups[(x)])
25680f86c9fSJeff Roberson #else	/* !SMP */
257ad1e7d28SJulian Elischer static struct tdq	tdq_cpu;
258dc03363dSJeff Roberson 
25936b36916SJeff Roberson #define	TDQ_ID(x)	(0)
260ad1e7d28SJulian Elischer #define	TDQ_SELF()	(&tdq_cpu)
261ad1e7d28SJulian Elischer #define	TDQ_CPU(x)	(&tdq_cpu)
2620a016a05SJeff Roberson #endif
26335e6168fSJeff Roberson 
264ae7a6b38SJeff Roberson #define	TDQ_LOCK_ASSERT(t, type)	mtx_assert(TDQ_LOCKPTR((t)), (type))
265ae7a6b38SJeff Roberson #define	TDQ_LOCK(t)		mtx_lock_spin(TDQ_LOCKPTR((t)))
266ae7a6b38SJeff Roberson #define	TDQ_LOCK_FLAGS(t, f)	mtx_lock_spin_flags(TDQ_LOCKPTR((t)), (f))
267ae7a6b38SJeff Roberson #define	TDQ_UNLOCK(t)		mtx_unlock_spin(TDQ_LOCKPTR((t)))
268ae7a6b38SJeff Roberson #define	TDQ_LOCKPTR(t)		(&(t)->tdq_lock)
269ae7a6b38SJeff Roberson 
2708460a577SJohn Birrell static void sched_priority(struct thread *);
27121381d1bSJeff Roberson static void sched_thread_priority(struct thread *, u_char);
2728460a577SJohn Birrell static int sched_interact_score(struct thread *);
2738460a577SJohn Birrell static void sched_interact_update(struct thread *);
2748460a577SJohn Birrell static void sched_interact_fork(struct thread *);
275ad1e7d28SJulian Elischer static void sched_pctcpu_update(struct td_sched *);
27635e6168fSJeff Roberson 
2775d7ef00cSJeff Roberson /* Operations on per processor queues */
278ad1e7d28SJulian Elischer static struct td_sched * tdq_choose(struct tdq *);
279ad1e7d28SJulian Elischer static void tdq_setup(struct tdq *);
280ad1e7d28SJulian Elischer static void tdq_load_add(struct tdq *, struct td_sched *);
281ad1e7d28SJulian Elischer static void tdq_load_rem(struct tdq *, struct td_sched *);
282ad1e7d28SJulian Elischer static __inline void tdq_runq_add(struct tdq *, struct td_sched *, int);
283ad1e7d28SJulian Elischer static __inline void tdq_runq_rem(struct tdq *, struct td_sched *);
284ad1e7d28SJulian Elischer void tdq_print(int cpu);
285e7d50326SJeff Roberson static void runq_print(struct runq *rq);
286ae7a6b38SJeff Roberson static void tdq_add(struct tdq *, struct thread *, int);
2875d7ef00cSJeff Roberson #ifdef SMP
288ae7a6b38SJeff Roberson static void tdq_move(struct tdq *, struct tdq *);
289ad1e7d28SJulian Elischer static int tdq_idled(struct tdq *);
2907b8bfa0dSJeff Roberson static void tdq_notify(struct td_sched *);
291ad1e7d28SJulian Elischer static struct td_sched *tdq_steal(struct tdq *, int);
292ae7a6b38SJeff Roberson static struct td_sched *runq_steal(struct runq *);
293ae7a6b38SJeff Roberson static int sched_pickcpu(struct td_sched *, int);
294ae7a6b38SJeff Roberson static void sched_balance(void *);
295ae7a6b38SJeff Roberson static void sched_balance_groups(void *);
296ae7a6b38SJeff Roberson static void sched_balance_group(struct tdq_group *);
297ae7a6b38SJeff Roberson static void sched_balance_pair(struct tdq *, struct tdq *);
298ae7a6b38SJeff Roberson static inline struct tdq *sched_setcpu(struct td_sched *, int, int);
299ae7a6b38SJeff Roberson static inline struct mtx *thread_block_switch(struct thread *);
300ae7a6b38SJeff Roberson static inline void thread_unblock_switch(struct thread *, struct mtx *);
3011e516cf5SJeff Roberson 
3027b8bfa0dSJeff Roberson #define	THREAD_CAN_MIGRATE(td)	 ((td)->td_pinned == 0)
3035d7ef00cSJeff Roberson #endif
3045d7ef00cSJeff Roberson 
305e7d50326SJeff Roberson static void sched_setup(void *dummy);
306e7d50326SJeff Roberson SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
307e7d50326SJeff Roberson 
308e7d50326SJeff Roberson static void sched_initticks(void *dummy);
309e7d50326SJeff Roberson SYSINIT(sched_initticks, SI_SUB_CLOCKS, SI_ORDER_THIRD, sched_initticks, NULL)
310e7d50326SJeff Roberson 
311ae7a6b38SJeff Roberson /*
312ae7a6b38SJeff Roberson  * Print the threads waiting on a run-queue.
313ae7a6b38SJeff Roberson  */
314e7d50326SJeff Roberson static void
315e7d50326SJeff Roberson runq_print(struct runq *rq)
316e7d50326SJeff Roberson {
317e7d50326SJeff Roberson 	struct rqhead *rqh;
318e7d50326SJeff Roberson 	struct td_sched *ts;
319e7d50326SJeff Roberson 	int pri;
320e7d50326SJeff Roberson 	int j;
321e7d50326SJeff Roberson 	int i;
322e7d50326SJeff Roberson 
323e7d50326SJeff Roberson 	for (i = 0; i < RQB_LEN; i++) {
324e7d50326SJeff Roberson 		printf("\t\trunq bits %d 0x%zx\n",
325e7d50326SJeff Roberson 		    i, rq->rq_status.rqb_bits[i]);
326e7d50326SJeff Roberson 		for (j = 0; j < RQB_BPW; j++)
327e7d50326SJeff Roberson 			if (rq->rq_status.rqb_bits[i] & (1ul << j)) {
328e7d50326SJeff Roberson 				pri = j + (i << RQB_L2BPW);
329e7d50326SJeff Roberson 				rqh = &rq->rq_queues[pri];
330e7d50326SJeff Roberson 				TAILQ_FOREACH(ts, rqh, ts_procq) {
331e7d50326SJeff Roberson 					printf("\t\t\ttd %p(%s) priority %d rqindex %d pri %d\n",
332e7d50326SJeff Roberson 					    ts->ts_thread, ts->ts_thread->td_proc->p_comm, ts->ts_thread->td_priority, ts->ts_rqindex, pri);
333e7d50326SJeff Roberson 				}
334e7d50326SJeff Roberson 			}
335e7d50326SJeff Roberson 	}
336e7d50326SJeff Roberson }
337e7d50326SJeff Roberson 
338ae7a6b38SJeff Roberson /*
339ae7a6b38SJeff Roberson  * Print the status of a per-cpu thread queue.  Should be a ddb show cmd.
340ae7a6b38SJeff Roberson  */
34115dc847eSJeff Roberson void
342ad1e7d28SJulian Elischer tdq_print(int cpu)
34315dc847eSJeff Roberson {
344ad1e7d28SJulian Elischer 	struct tdq *tdq;
34515dc847eSJeff Roberson 
346ad1e7d28SJulian Elischer 	tdq = TDQ_CPU(cpu);
34715dc847eSJeff Roberson 
348ad1e7d28SJulian Elischer 	printf("tdq:\n");
349ae7a6b38SJeff Roberson 	printf("\tlockptr         %p\n", TDQ_LOCKPTR(tdq));
350ae7a6b38SJeff Roberson 	printf("\tlock name       %s\n", tdq->tdq_name);
351d2ad694cSJeff Roberson 	printf("\tload:           %d\n", tdq->tdq_load);
352e7d50326SJeff Roberson 	printf("\ttimeshare idx:  %d\n", tdq->tdq_idx);
3533f872f85SJeff Roberson 	printf("\ttimeshare ridx: %d\n", tdq->tdq_ridx);
354e7d50326SJeff Roberson 	printf("\trealtime runq:\n");
355e7d50326SJeff Roberson 	runq_print(&tdq->tdq_realtime);
356e7d50326SJeff Roberson 	printf("\ttimeshare runq:\n");
357e7d50326SJeff Roberson 	runq_print(&tdq->tdq_timeshare);
358e7d50326SJeff Roberson 	printf("\tidle runq:\n");
359e7d50326SJeff Roberson 	runq_print(&tdq->tdq_idle);
360ef1134c9SJeff Roberson #ifdef SMP
361d2ad694cSJeff Roberson 	printf("\tload transferable: %d\n", tdq->tdq_transferable);
362ae7a6b38SJeff Roberson 	printf("\tlowest priority: %d\n", tdq->tdq_lowpri);
363ef1134c9SJeff Roberson #endif
36415dc847eSJeff Roberson }
36515dc847eSJeff Roberson 
366ae7a6b38SJeff Roberson #define	TS_RQ_PPQ	(((PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE) + 1) / RQ_NQS)
367ae7a6b38SJeff Roberson /*
368ae7a6b38SJeff Roberson  * Add a thread to the actual run-queue.  Keeps transferable counts up to
369ae7a6b38SJeff Roberson  * date with what is actually on the run-queue.  Selects the correct
370ae7a6b38SJeff Roberson  * queue position for timeshare threads.
371ae7a6b38SJeff Roberson  */
372155b9987SJeff Roberson static __inline void
373ad1e7d28SJulian Elischer tdq_runq_add(struct tdq *tdq, struct td_sched *ts, int flags)
374155b9987SJeff Roberson {
375ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
376ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
377155b9987SJeff Roberson #ifdef SMP
378e7d50326SJeff Roberson 	if (THREAD_CAN_MIGRATE(ts->ts_thread)) {
379d2ad694cSJeff Roberson 		tdq->tdq_transferable++;
380d2ad694cSJeff Roberson 		tdq->tdq_group->tdg_transferable++;
381ad1e7d28SJulian Elischer 		ts->ts_flags |= TSF_XFERABLE;
38280f86c9fSJeff Roberson 	}
383155b9987SJeff Roberson #endif
384e7d50326SJeff Roberson 	if (ts->ts_runq == &tdq->tdq_timeshare) {
385ed0e8f2fSJeff Roberson 		u_char pri;
386e7d50326SJeff Roberson 
387e7d50326SJeff Roberson 		pri = ts->ts_thread->td_priority;
388e7d50326SJeff Roberson 		KASSERT(pri <= PRI_MAX_TIMESHARE && pri >= PRI_MIN_TIMESHARE,
389e7d50326SJeff Roberson 			("Invalid priority %d on timeshare runq", pri));
390e7d50326SJeff Roberson 		/*
391e7d50326SJeff Roberson 		 * This queue contains only priorities between MIN and MAX
392e7d50326SJeff Roberson 		 * realtime.  Use the whole queue to represent these values.
393e7d50326SJeff Roberson 		 */
394e7d50326SJeff Roberson 		if ((flags & SRQ_BORROWING) == 0) {
395e7d50326SJeff Roberson 			pri = (pri - PRI_MIN_TIMESHARE) / TS_RQ_PPQ;
396e7d50326SJeff Roberson 			pri = (pri + tdq->tdq_idx) % RQ_NQS;
3973f872f85SJeff Roberson 			/*
3983f872f85SJeff Roberson 			 * This effectively shortens the queue by one so we
3993f872f85SJeff Roberson 			 * can have a one slot difference between idx and
4003f872f85SJeff Roberson 			 * ridx while we wait for threads to drain.
4013f872f85SJeff Roberson 			 */
4023f872f85SJeff Roberson 			if (tdq->tdq_ridx != tdq->tdq_idx &&
4033f872f85SJeff Roberson 			    pri == tdq->tdq_ridx)
4044499aff6SJeff Roberson 				pri = (unsigned char)(pri - 1) % RQ_NQS;
405e7d50326SJeff Roberson 		} else
4063f872f85SJeff Roberson 			pri = tdq->tdq_ridx;
407e7d50326SJeff Roberson 		runq_add_pri(ts->ts_runq, ts, pri, flags);
408e7d50326SJeff Roberson 	} else
409ad1e7d28SJulian Elischer 		runq_add(ts->ts_runq, ts, flags);
410155b9987SJeff Roberson }
411155b9987SJeff Roberson 
412ae7a6b38SJeff Roberson /*
413ae7a6b38SJeff Roberson  * Remove a thread from a run-queue.  This typically happens when a thread
414ae7a6b38SJeff Roberson  * is selected to run.  Running threads are not on the queue and the
415ae7a6b38SJeff Roberson  * transferable count does not reflect them.
416ae7a6b38SJeff Roberson  */
417155b9987SJeff Roberson static __inline void
418ad1e7d28SJulian Elischer tdq_runq_rem(struct tdq *tdq, struct td_sched *ts)
419155b9987SJeff Roberson {
420ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
421ae7a6b38SJeff Roberson 	KASSERT(ts->ts_runq != NULL,
422ae7a6b38SJeff Roberson 	    ("tdq_runq_remove: thread %p null ts_runq", ts->ts_thread));
423155b9987SJeff Roberson #ifdef SMP
424ad1e7d28SJulian Elischer 	if (ts->ts_flags & TSF_XFERABLE) {
425d2ad694cSJeff Roberson 		tdq->tdq_transferable--;
426d2ad694cSJeff Roberson 		tdq->tdq_group->tdg_transferable--;
427ad1e7d28SJulian Elischer 		ts->ts_flags &= ~TSF_XFERABLE;
42880f86c9fSJeff Roberson 	}
429155b9987SJeff Roberson #endif
4303f872f85SJeff Roberson 	if (ts->ts_runq == &tdq->tdq_timeshare) {
4313f872f85SJeff Roberson 		if (tdq->tdq_idx != tdq->tdq_ridx)
4323f872f85SJeff Roberson 			runq_remove_idx(ts->ts_runq, ts, &tdq->tdq_ridx);
433e7d50326SJeff Roberson 		else
4343f872f85SJeff Roberson 			runq_remove_idx(ts->ts_runq, ts, NULL);
4358ab80cf0SJeff Roberson 		/*
4368ab80cf0SJeff Roberson 		 * For timeshare threads we update the priority here so
4378ab80cf0SJeff Roberson 		 * the priority reflects the time we've been sleeping.
4388ab80cf0SJeff Roberson 		 */
4398ab80cf0SJeff Roberson 		ts->ts_ltick = ticks;
4408ab80cf0SJeff Roberson 		sched_pctcpu_update(ts);
4418ab80cf0SJeff Roberson 		sched_priority(ts->ts_thread);
4423f872f85SJeff Roberson 	} else
443ad1e7d28SJulian Elischer 		runq_remove(ts->ts_runq, ts);
444155b9987SJeff Roberson }
445155b9987SJeff Roberson 
446ae7a6b38SJeff Roberson /*
447ae7a6b38SJeff Roberson  * Load is maintained for all threads RUNNING and ON_RUNQ.  Add the load
448ae7a6b38SJeff Roberson  * for this thread to the referenced thread queue.
449ae7a6b38SJeff Roberson  */
450a8949de2SJeff Roberson static void
451ad1e7d28SJulian Elischer tdq_load_add(struct tdq *tdq, struct td_sched *ts)
4525d7ef00cSJeff Roberson {
453ef1134c9SJeff Roberson 	int class;
454ae7a6b38SJeff Roberson 
455ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
456ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
457ad1e7d28SJulian Elischer 	class = PRI_BASE(ts->ts_thread->td_pri_class);
458d2ad694cSJeff Roberson 	tdq->tdq_load++;
4597b20fb19SJeff Roberson 	CTR2(KTR_SCHED, "cpu %jd load: %d", TDQ_ID(tdq), tdq->tdq_load);
4607b8bfa0dSJeff Roberson 	if (class != PRI_ITHD &&
4617b8bfa0dSJeff Roberson 	    (ts->ts_thread->td_proc->p_flag & P_NOLOAD) == 0)
46233916c36SJeff Roberson #ifdef SMP
463d2ad694cSJeff Roberson 		tdq->tdq_group->tdg_load++;
46433916c36SJeff Roberson #else
465d2ad694cSJeff Roberson 		tdq->tdq_sysload++;
466cac77d04SJeff Roberson #endif
4675d7ef00cSJeff Roberson }
46815dc847eSJeff Roberson 
469ae7a6b38SJeff Roberson /*
470ae7a6b38SJeff Roberson  * Remove the load from a thread that is transitioning to a sleep state or
471ae7a6b38SJeff Roberson  * exiting.
472ae7a6b38SJeff Roberson  */
473a8949de2SJeff Roberson static void
474ad1e7d28SJulian Elischer tdq_load_rem(struct tdq *tdq, struct td_sched *ts)
4755d7ef00cSJeff Roberson {
476ef1134c9SJeff Roberson 	int class;
477ae7a6b38SJeff Roberson 
478ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
479ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
480ad1e7d28SJulian Elischer 	class = PRI_BASE(ts->ts_thread->td_pri_class);
4817b8bfa0dSJeff Roberson 	if (class != PRI_ITHD &&
4827b8bfa0dSJeff Roberson 	    (ts->ts_thread->td_proc->p_flag & P_NOLOAD) == 0)
48333916c36SJeff Roberson #ifdef SMP
484d2ad694cSJeff Roberson 		tdq->tdq_group->tdg_load--;
48533916c36SJeff Roberson #else
486d2ad694cSJeff Roberson 		tdq->tdq_sysload--;
487cac77d04SJeff Roberson #endif
488ae7a6b38SJeff Roberson 	KASSERT(tdq->tdq_load != 0,
489ae7a6b38SJeff Roberson 	    ("tdq_load_rem: Removing with 0 load on queue %d", (int)TDQ_ID(tdq)));
490d2ad694cSJeff Roberson 	tdq->tdq_load--;
491d2ad694cSJeff Roberson 	CTR1(KTR_SCHED, "load: %d", tdq->tdq_load);
492ad1e7d28SJulian Elischer 	ts->ts_runq = NULL;
49315dc847eSJeff Roberson }
49415dc847eSJeff Roberson 
4955d7ef00cSJeff Roberson #ifdef SMP
496356500a3SJeff Roberson /*
497155b9987SJeff Roberson  * sched_balance is a simple CPU load balancing algorithm.  It operates by
498356500a3SJeff Roberson  * finding the least loaded and most loaded cpu and equalizing their load
499356500a3SJeff Roberson  * by migrating some processes.
500356500a3SJeff Roberson  *
501356500a3SJeff Roberson  * Dealing only with two CPUs at a time has two advantages.  Firstly, most
502356500a3SJeff Roberson  * installations will only have 2 cpus.  Secondly, load balancing too much at
503356500a3SJeff Roberson  * once can have an unpleasant effect on the system.  The scheduler rarely has
504356500a3SJeff Roberson  * enough information to make perfect decisions.  So this algorithm chooses
505ae7a6b38SJeff Roberson  * simplicity and more gradual effects on load in larger systems.
506356500a3SJeff Roberson  *
507356500a3SJeff Roberson  */
50822bf7d9aSJeff Roberson static void
509ae7a6b38SJeff Roberson sched_balance(void *arg)
510356500a3SJeff Roberson {
511ad1e7d28SJulian Elischer 	struct tdq_group *high;
512ad1e7d28SJulian Elischer 	struct tdq_group *low;
513d2ad694cSJeff Roberson 	struct tdq_group *tdg;
514cac77d04SJeff Roberson 	int cnt;
515356500a3SJeff Roberson 	int i;
516356500a3SJeff Roberson 
517ae7a6b38SJeff Roberson 	callout_reset(&balco, max(hz / 2, random() % (hz * SCHED_BAL_SECS)),
518ae7a6b38SJeff Roberson 	    sched_balance, NULL);
519ae7a6b38SJeff Roberson 	if (smp_started == 0 || rebalance == 0)
520598b368dSJeff Roberson 		return;
521cac77d04SJeff Roberson 	low = high = NULL;
522d2ad694cSJeff Roberson 	i = random() % (tdg_maxid + 1);
523d2ad694cSJeff Roberson 	for (cnt = 0; cnt <= tdg_maxid; cnt++) {
524d2ad694cSJeff Roberson 		tdg = TDQ_GROUP(i);
525cac77d04SJeff Roberson 		/*
526cac77d04SJeff Roberson 		 * Find the CPU with the highest load that has some
527cac77d04SJeff Roberson 		 * threads to transfer.
528cac77d04SJeff Roberson 		 */
529d2ad694cSJeff Roberson 		if ((high == NULL || tdg->tdg_load > high->tdg_load)
530d2ad694cSJeff Roberson 		    && tdg->tdg_transferable)
531d2ad694cSJeff Roberson 			high = tdg;
532d2ad694cSJeff Roberson 		if (low == NULL || tdg->tdg_load < low->tdg_load)
533d2ad694cSJeff Roberson 			low = tdg;
534d2ad694cSJeff Roberson 		if (++i > tdg_maxid)
535cac77d04SJeff Roberson 			i = 0;
536cac77d04SJeff Roberson 	}
537cac77d04SJeff Roberson 	if (low != NULL && high != NULL && high != low)
538d2ad694cSJeff Roberson 		sched_balance_pair(LIST_FIRST(&high->tdg_members),
539d2ad694cSJeff Roberson 		    LIST_FIRST(&low->tdg_members));
540cac77d04SJeff Roberson }
54186f8ae96SJeff Roberson 
542ae7a6b38SJeff Roberson /*
543ae7a6b38SJeff Roberson  * Balance load between CPUs in a group.  Will only migrate within the group.
544ae7a6b38SJeff Roberson  */
545cac77d04SJeff Roberson static void
546ae7a6b38SJeff Roberson sched_balance_groups(void *arg)
547cac77d04SJeff Roberson {
548cac77d04SJeff Roberson 	int i;
549cac77d04SJeff Roberson 
550ae7a6b38SJeff Roberson 	callout_reset(&gbalco, max(hz / 2, random() % (hz * SCHED_BAL_SECS)),
551ae7a6b38SJeff Roberson 	    sched_balance_groups, NULL);
552ae7a6b38SJeff Roberson 	if (smp_started == 0 || rebalance == 0)
553ae7a6b38SJeff Roberson 		return;
554d2ad694cSJeff Roberson 	for (i = 0; i <= tdg_maxid; i++)
555ad1e7d28SJulian Elischer 		sched_balance_group(TDQ_GROUP(i));
556356500a3SJeff Roberson }
557cac77d04SJeff Roberson 
558ae7a6b38SJeff Roberson /*
559ae7a6b38SJeff Roberson  * Finds the greatest imbalance between two tdqs in a group.
560ae7a6b38SJeff Roberson  */
561cac77d04SJeff Roberson static void
562d2ad694cSJeff Roberson sched_balance_group(struct tdq_group *tdg)
563cac77d04SJeff Roberson {
564ad1e7d28SJulian Elischer 	struct tdq *tdq;
565ad1e7d28SJulian Elischer 	struct tdq *high;
566ad1e7d28SJulian Elischer 	struct tdq *low;
567cac77d04SJeff Roberson 	int load;
568cac77d04SJeff Roberson 
569d2ad694cSJeff Roberson 	if (tdg->tdg_transferable == 0)
570cac77d04SJeff Roberson 		return;
571cac77d04SJeff Roberson 	low = NULL;
572cac77d04SJeff Roberson 	high = NULL;
573d2ad694cSJeff Roberson 	LIST_FOREACH(tdq, &tdg->tdg_members, tdq_siblings) {
574d2ad694cSJeff Roberson 		load = tdq->tdq_load;
575d2ad694cSJeff Roberson 		if (high == NULL || load > high->tdq_load)
576ad1e7d28SJulian Elischer 			high = tdq;
577d2ad694cSJeff Roberson 		if (low == NULL || load < low->tdq_load)
578ad1e7d28SJulian Elischer 			low = tdq;
579356500a3SJeff Roberson 	}
580cac77d04SJeff Roberson 	if (high != NULL && low != NULL && high != low)
581cac77d04SJeff Roberson 		sched_balance_pair(high, low);
582356500a3SJeff Roberson }
583cac77d04SJeff Roberson 
584ae7a6b38SJeff Roberson /*
585ae7a6b38SJeff Roberson  * Lock two thread queues using their address to maintain lock order.
586ae7a6b38SJeff Roberson  */
587ae7a6b38SJeff Roberson static void
588ae7a6b38SJeff Roberson tdq_lock_pair(struct tdq *one, struct tdq *two)
589ae7a6b38SJeff Roberson {
590ae7a6b38SJeff Roberson 	if (one < two) {
591ae7a6b38SJeff Roberson 		TDQ_LOCK(one);
592ae7a6b38SJeff Roberson 		TDQ_LOCK_FLAGS(two, MTX_DUPOK);
593ae7a6b38SJeff Roberson 	} else {
594ae7a6b38SJeff Roberson 		TDQ_LOCK(two);
595ae7a6b38SJeff Roberson 		TDQ_LOCK_FLAGS(one, MTX_DUPOK);
596ae7a6b38SJeff Roberson 	}
597ae7a6b38SJeff Roberson }
598ae7a6b38SJeff Roberson 
599ae7a6b38SJeff Roberson /*
600ae7a6b38SJeff Roberson  * Transfer load between two imbalanced thread queues.
601ae7a6b38SJeff Roberson  */
602cac77d04SJeff Roberson static void
603ad1e7d28SJulian Elischer sched_balance_pair(struct tdq *high, struct tdq *low)
604cac77d04SJeff Roberson {
605cac77d04SJeff Roberson 	int transferable;
606cac77d04SJeff Roberson 	int high_load;
607cac77d04SJeff Roberson 	int low_load;
608cac77d04SJeff Roberson 	int move;
609cac77d04SJeff Roberson 	int diff;
610cac77d04SJeff Roberson 	int i;
611cac77d04SJeff Roberson 
612ae7a6b38SJeff Roberson 	tdq_lock_pair(high, low);
61380f86c9fSJeff Roberson 	/*
61480f86c9fSJeff Roberson 	 * If we're transfering within a group we have to use this specific
615ad1e7d28SJulian Elischer 	 * tdq's transferable count, otherwise we can steal from other members
61680f86c9fSJeff Roberson 	 * of the group.
61780f86c9fSJeff Roberson 	 */
618d2ad694cSJeff Roberson 	if (high->tdq_group == low->tdq_group) {
619d2ad694cSJeff Roberson 		transferable = high->tdq_transferable;
620d2ad694cSJeff Roberson 		high_load = high->tdq_load;
621d2ad694cSJeff Roberson 		low_load = low->tdq_load;
622cac77d04SJeff Roberson 	} else {
623d2ad694cSJeff Roberson 		transferable = high->tdq_group->tdg_transferable;
624d2ad694cSJeff Roberson 		high_load = high->tdq_group->tdg_load;
625d2ad694cSJeff Roberson 		low_load = low->tdq_group->tdg_load;
626cac77d04SJeff Roberson 	}
627155b9987SJeff Roberson 	/*
628155b9987SJeff Roberson 	 * Determine what the imbalance is and then adjust that to how many
629d2ad694cSJeff Roberson 	 * threads we actually have to give up (transferable).
630155b9987SJeff Roberson 	 */
631ae7a6b38SJeff Roberson 	if (transferable != 0) {
632cac77d04SJeff Roberson 		diff = high_load - low_load;
633356500a3SJeff Roberson 		move = diff / 2;
634356500a3SJeff Roberson 		if (diff & 0x1)
635356500a3SJeff Roberson 			move++;
63680f86c9fSJeff Roberson 		move = min(move, transferable);
637356500a3SJeff Roberson 		for (i = 0; i < move; i++)
638ae7a6b38SJeff Roberson 			tdq_move(high, low);
639ae7a6b38SJeff Roberson 	}
640ae7a6b38SJeff Roberson 	TDQ_UNLOCK(high);
641ae7a6b38SJeff Roberson 	TDQ_UNLOCK(low);
642356500a3SJeff Roberson 	return;
643356500a3SJeff Roberson }
644356500a3SJeff Roberson 
645ae7a6b38SJeff Roberson /*
646ae7a6b38SJeff Roberson  * Move a thread from one thread queue to another.
647ae7a6b38SJeff Roberson  */
64822bf7d9aSJeff Roberson static void
649ae7a6b38SJeff Roberson tdq_move(struct tdq *from, struct tdq *to)
650356500a3SJeff Roberson {
651ad1e7d28SJulian Elischer 	struct td_sched *ts;
652ae7a6b38SJeff Roberson 	struct thread *td;
653ae7a6b38SJeff Roberson 	struct tdq *tdq;
654ae7a6b38SJeff Roberson 	int cpu;
655356500a3SJeff Roberson 
656ad1e7d28SJulian Elischer 	tdq = from;
657ae7a6b38SJeff Roberson 	cpu = TDQ_ID(to);
658ad1e7d28SJulian Elischer 	ts = tdq_steal(tdq, 1);
659ad1e7d28SJulian Elischer 	if (ts == NULL) {
660d2ad694cSJeff Roberson 		struct tdq_group *tdg;
66180f86c9fSJeff Roberson 
662d2ad694cSJeff Roberson 		tdg = tdq->tdq_group;
663d2ad694cSJeff Roberson 		LIST_FOREACH(tdq, &tdg->tdg_members, tdq_siblings) {
664d2ad694cSJeff Roberson 			if (tdq == from || tdq->tdq_transferable == 0)
66580f86c9fSJeff Roberson 				continue;
666ad1e7d28SJulian Elischer 			ts = tdq_steal(tdq, 1);
66780f86c9fSJeff Roberson 			break;
66880f86c9fSJeff Roberson 		}
669ad1e7d28SJulian Elischer 		if (ts == NULL)
670ae7a6b38SJeff Roberson 			return;
67180f86c9fSJeff Roberson 	}
672ad1e7d28SJulian Elischer 	if (tdq == to)
67380f86c9fSJeff Roberson 		return;
674ae7a6b38SJeff Roberson 	td = ts->ts_thread;
675ae7a6b38SJeff Roberson 	/*
676ae7a6b38SJeff Roberson 	 * Although the run queue is locked the thread may be blocked.  Lock
677ae7a6b38SJeff Roberson 	 * it to clear this.
678ae7a6b38SJeff Roberson 	 */
679ae7a6b38SJeff Roberson 	thread_lock(td);
680ae7a6b38SJeff Roberson 	/* Drop recursive lock on from. */
681ae7a6b38SJeff Roberson 	TDQ_UNLOCK(from);
682ae7a6b38SJeff Roberson 	sched_rem(td);
6837b8bfa0dSJeff Roberson 	ts->ts_cpu = cpu;
684ae7a6b38SJeff Roberson 	td->td_lock = TDQ_LOCKPTR(to);
685ae7a6b38SJeff Roberson 	tdq_add(to, td, SRQ_YIELDING);
686356500a3SJeff Roberson }
68722bf7d9aSJeff Roberson 
688ae7a6b38SJeff Roberson /*
689ae7a6b38SJeff Roberson  * This tdq has idled.  Try to steal a thread from another cpu and switch
690ae7a6b38SJeff Roberson  * to it.
691ae7a6b38SJeff Roberson  */
69280f86c9fSJeff Roberson static int
693ad1e7d28SJulian Elischer tdq_idled(struct tdq *tdq)
69422bf7d9aSJeff Roberson {
695d2ad694cSJeff Roberson 	struct tdq_group *tdg;
696ad1e7d28SJulian Elischer 	struct tdq *steal;
697ad1e7d28SJulian Elischer 	struct td_sched *ts;
698ae7a6b38SJeff Roberson 	struct thread *td;
699ae7a6b38SJeff Roberson 	int highload;
700ae7a6b38SJeff Roberson 	int highcpu;
701ae7a6b38SJeff Roberson 	int load;
702ae7a6b38SJeff Roberson 	int cpu;
70380f86c9fSJeff Roberson 
704ae7a6b38SJeff Roberson 	/* We don't want to be preempted while we're iterating over tdqs */
705ae7a6b38SJeff Roberson 	spinlock_enter();
706d2ad694cSJeff Roberson 	tdg = tdq->tdq_group;
70780f86c9fSJeff Roberson 	/*
708d2ad694cSJeff Roberson 	 * If we're in a cpu group, try and steal threads from another cpu in
70980f86c9fSJeff Roberson 	 * the group before idling.
71080f86c9fSJeff Roberson 	 */
7117b8bfa0dSJeff Roberson 	if (steal_htt && tdg->tdg_cpus > 1 && tdg->tdg_transferable) {
712d2ad694cSJeff Roberson 		LIST_FOREACH(steal, &tdg->tdg_members, tdq_siblings) {
713d2ad694cSJeff Roberson 			if (steal == tdq || steal->tdq_transferable == 0)
71480f86c9fSJeff Roberson 				continue;
715ae7a6b38SJeff Roberson 			TDQ_LOCK(steal);
716ad1e7d28SJulian Elischer 			ts = tdq_steal(steal, 0);
7177b8bfa0dSJeff Roberson 			if (ts)
7187b8bfa0dSJeff Roberson 				goto steal;
719ae7a6b38SJeff Roberson 			TDQ_UNLOCK(steal);
7207b8bfa0dSJeff Roberson 		}
7217b8bfa0dSJeff Roberson 	}
722ae7a6b38SJeff Roberson 	for (;;) {
723ae7a6b38SJeff Roberson 		if (steal_idle == 0)
7247b8bfa0dSJeff Roberson 			break;
725ae7a6b38SJeff Roberson 		highcpu = 0;
726ae7a6b38SJeff Roberson 		highload = 0;
727ae7a6b38SJeff Roberson 		for (cpu = 0; cpu <= mp_maxid; cpu++) {
728ae7a6b38SJeff Roberson 			if (CPU_ABSENT(cpu))
729ae7a6b38SJeff Roberson 				continue;
7307b8bfa0dSJeff Roberson 			steal = TDQ_CPU(cpu);
731ae7a6b38SJeff Roberson 			load = TDQ_CPU(cpu)->tdq_transferable;
732ae7a6b38SJeff Roberson 			if (load < highload)
7337b8bfa0dSJeff Roberson 				continue;
734ae7a6b38SJeff Roberson 			highload = load;
735ae7a6b38SJeff Roberson 			highcpu = cpu;
736ae7a6b38SJeff Roberson 		}
737ae7a6b38SJeff Roberson 		if (highload < 2)
738ae7a6b38SJeff Roberson 			break;
739ae7a6b38SJeff Roberson 		steal = TDQ_CPU(highcpu);
740ae7a6b38SJeff Roberson 		TDQ_LOCK(steal);
741ae7a6b38SJeff Roberson 		if (steal->tdq_transferable > 1 &&
742ae7a6b38SJeff Roberson 		    (ts = tdq_steal(steal, 1)) != NULL)
7437b8bfa0dSJeff Roberson 			goto steal;
744ae7a6b38SJeff Roberson 		TDQ_UNLOCK(steal);
745ae7a6b38SJeff Roberson 		break;
74680f86c9fSJeff Roberson 	}
747ae7a6b38SJeff Roberson 	spinlock_exit();
74880f86c9fSJeff Roberson 	return (1);
7497b8bfa0dSJeff Roberson steal:
750ae7a6b38SJeff Roberson 	td = ts->ts_thread;
751ae7a6b38SJeff Roberson 	thread_lock(td);
752ae7a6b38SJeff Roberson 	spinlock_exit();
753ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(steal));
754ae7a6b38SJeff Roberson 	TDQ_UNLOCK(steal);
755ae7a6b38SJeff Roberson 	sched_rem(td);
756ae7a6b38SJeff Roberson 	sched_setcpu(ts, PCPU_GET(cpuid), SRQ_YIELDING);
757ae7a6b38SJeff Roberson 	tdq_add(tdq, td, SRQ_YIELDING);
758ae7a6b38SJeff Roberson 	MPASS(td->td_lock == curthread->td_lock);
759ae7a6b38SJeff Roberson 	mi_switch(SW_VOL, NULL);
760ae7a6b38SJeff Roberson 	thread_unlock(curthread);
7617b8bfa0dSJeff Roberson 
7627b8bfa0dSJeff Roberson 	return (0);
76322bf7d9aSJeff Roberson }
76422bf7d9aSJeff Roberson 
765ae7a6b38SJeff Roberson /*
766ae7a6b38SJeff Roberson  * Notify a remote cpu of new work.  Sends an IPI if criteria are met.
767ae7a6b38SJeff Roberson  */
76822bf7d9aSJeff Roberson static void
7697b8bfa0dSJeff Roberson tdq_notify(struct td_sched *ts)
77022bf7d9aSJeff Roberson {
771fc3a97dcSJeff Roberson 	struct thread *ctd;
77222bf7d9aSJeff Roberson 	struct pcpu *pcpu;
773fc3a97dcSJeff Roberson 	int cpri;
774fc3a97dcSJeff Roberson 	int pri;
7757b8bfa0dSJeff Roberson 	int cpu;
77622bf7d9aSJeff Roberson 
7777b8bfa0dSJeff Roberson 	cpu = ts->ts_cpu;
778fc3a97dcSJeff Roberson 	pri = ts->ts_thread->td_priority;
77922bf7d9aSJeff Roberson 	pcpu = pcpu_find(cpu);
780fc3a97dcSJeff Roberson 	ctd = pcpu->pc_curthread;
781fc3a97dcSJeff Roberson 	cpri = ctd->td_priority;
7826b2f763fSJeff Roberson 
7836b2f763fSJeff Roberson 	/*
7846b2f763fSJeff Roberson 	 * If our priority is not better than the current priority there is
7856b2f763fSJeff Roberson 	 * nothing to do.
7866b2f763fSJeff Roberson 	 */
787fc3a97dcSJeff Roberson 	if (pri > cpri)
7886b2f763fSJeff Roberson 		return;
7897b8bfa0dSJeff Roberson 	/*
790fc3a97dcSJeff Roberson 	 * Always IPI idle.
7917b8bfa0dSJeff Roberson 	 */
792fc3a97dcSJeff Roberson 	if (cpri > PRI_MIN_IDLE)
793fc3a97dcSJeff Roberson 		goto sendipi;
794fc3a97dcSJeff Roberson 	/*
795fc3a97dcSJeff Roberson 	 * If we're realtime or better and there is timeshare or worse running
796fc3a97dcSJeff Roberson 	 * send an IPI.
797fc3a97dcSJeff Roberson 	 */
798fc3a97dcSJeff Roberson 	if (pri < PRI_MAX_REALTIME && cpri > PRI_MAX_REALTIME)
799fc3a97dcSJeff Roberson 		goto sendipi;
800fc3a97dcSJeff Roberson 	/*
801fc3a97dcSJeff Roberson 	 * Otherwise only IPI if we exceed the threshold.
802fc3a97dcSJeff Roberson 	 */
803ae7a6b38SJeff Roberson 	if (pri > preempt_thresh)
8047b8bfa0dSJeff Roberson 		return;
805fc3a97dcSJeff Roberson sendipi:
806fc3a97dcSJeff Roberson 	ctd->td_flags |= TDF_NEEDRESCHED;
80714618990SJeff Roberson 	ipi_selected(1 << cpu, IPI_PREEMPT);
80822bf7d9aSJeff Roberson }
80922bf7d9aSJeff Roberson 
810ae7a6b38SJeff Roberson /*
811ae7a6b38SJeff Roberson  * Steals load from a timeshare queue.  Honors the rotating queue head
812ae7a6b38SJeff Roberson  * index.
813ae7a6b38SJeff Roberson  */
814ae7a6b38SJeff Roberson static struct td_sched *
815ae7a6b38SJeff Roberson runq_steal_from(struct runq *rq, u_char start)
816ae7a6b38SJeff Roberson {
817ae7a6b38SJeff Roberson 	struct td_sched *ts;
818ae7a6b38SJeff Roberson 	struct rqbits *rqb;
819ae7a6b38SJeff Roberson 	struct rqhead *rqh;
820ae7a6b38SJeff Roberson 	int first;
821ae7a6b38SJeff Roberson 	int bit;
822ae7a6b38SJeff Roberson 	int pri;
823ae7a6b38SJeff Roberson 	int i;
824ae7a6b38SJeff Roberson 
825ae7a6b38SJeff Roberson 	rqb = &rq->rq_status;
826ae7a6b38SJeff Roberson 	bit = start & (RQB_BPW -1);
827ae7a6b38SJeff Roberson 	pri = 0;
828ae7a6b38SJeff Roberson 	first = 0;
829ae7a6b38SJeff Roberson again:
830ae7a6b38SJeff Roberson 	for (i = RQB_WORD(start); i < RQB_LEN; bit = 0, i++) {
831ae7a6b38SJeff Roberson 		if (rqb->rqb_bits[i] == 0)
832ae7a6b38SJeff Roberson 			continue;
833ae7a6b38SJeff Roberson 		if (bit != 0) {
834ae7a6b38SJeff Roberson 			for (pri = bit; pri < RQB_BPW; pri++)
835ae7a6b38SJeff Roberson 				if (rqb->rqb_bits[i] & (1ul << pri))
836ae7a6b38SJeff Roberson 					break;
837ae7a6b38SJeff Roberson 			if (pri >= RQB_BPW)
838ae7a6b38SJeff Roberson 				continue;
839ae7a6b38SJeff Roberson 		} else
840ae7a6b38SJeff Roberson 			pri = RQB_FFS(rqb->rqb_bits[i]);
841ae7a6b38SJeff Roberson 		pri += (i << RQB_L2BPW);
842ae7a6b38SJeff Roberson 		rqh = &rq->rq_queues[pri];
843ae7a6b38SJeff Roberson 		TAILQ_FOREACH(ts, rqh, ts_procq) {
844ae7a6b38SJeff Roberson 			if (first && THREAD_CAN_MIGRATE(ts->ts_thread))
845ae7a6b38SJeff Roberson 				return (ts);
846ae7a6b38SJeff Roberson 			first = 1;
847ae7a6b38SJeff Roberson 		}
848ae7a6b38SJeff Roberson 	}
849ae7a6b38SJeff Roberson 	if (start != 0) {
850ae7a6b38SJeff Roberson 		start = 0;
851ae7a6b38SJeff Roberson 		goto again;
852ae7a6b38SJeff Roberson 	}
853ae7a6b38SJeff Roberson 
854ae7a6b38SJeff Roberson 	return (NULL);
855ae7a6b38SJeff Roberson }
856ae7a6b38SJeff Roberson 
857ae7a6b38SJeff Roberson /*
858ae7a6b38SJeff Roberson  * Steals load from a standard linear queue.
859ae7a6b38SJeff Roberson  */
860ad1e7d28SJulian Elischer static struct td_sched *
86122bf7d9aSJeff Roberson runq_steal(struct runq *rq)
86222bf7d9aSJeff Roberson {
86322bf7d9aSJeff Roberson 	struct rqhead *rqh;
86422bf7d9aSJeff Roberson 	struct rqbits *rqb;
865ad1e7d28SJulian Elischer 	struct td_sched *ts;
866ae7a6b38SJeff Roberson 	int first;
86722bf7d9aSJeff Roberson 	int word;
86822bf7d9aSJeff Roberson 	int bit;
86922bf7d9aSJeff Roberson 
870ae7a6b38SJeff Roberson 	first = 0;
87122bf7d9aSJeff Roberson 	rqb = &rq->rq_status;
87222bf7d9aSJeff Roberson 	for (word = 0; word < RQB_LEN; word++) {
87322bf7d9aSJeff Roberson 		if (rqb->rqb_bits[word] == 0)
87422bf7d9aSJeff Roberson 			continue;
87522bf7d9aSJeff Roberson 		for (bit = 0; bit < RQB_BPW; bit++) {
876a2640c9bSPeter Wemm 			if ((rqb->rqb_bits[word] & (1ul << bit)) == 0)
87722bf7d9aSJeff Roberson 				continue;
87822bf7d9aSJeff Roberson 			rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
879ad1e7d28SJulian Elischer 			TAILQ_FOREACH(ts, rqh, ts_procq) {
880ae7a6b38SJeff Roberson 				if (first && THREAD_CAN_MIGRATE(ts->ts_thread))
881ad1e7d28SJulian Elischer 					return (ts);
882ae7a6b38SJeff Roberson 				first = 1;
88322bf7d9aSJeff Roberson 			}
88422bf7d9aSJeff Roberson 		}
88522bf7d9aSJeff Roberson 	}
88622bf7d9aSJeff Roberson 	return (NULL);
88722bf7d9aSJeff Roberson }
88822bf7d9aSJeff Roberson 
889ae7a6b38SJeff Roberson /*
890ae7a6b38SJeff Roberson  * Attempt to steal a thread in priority order from a thread queue.
891ae7a6b38SJeff Roberson  */
892ad1e7d28SJulian Elischer static struct td_sched *
893ad1e7d28SJulian Elischer tdq_steal(struct tdq *tdq, int stealidle)
89422bf7d9aSJeff Roberson {
895ad1e7d28SJulian Elischer 	struct td_sched *ts;
89622bf7d9aSJeff Roberson 
897ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
898e7d50326SJeff Roberson 	if ((ts = runq_steal(&tdq->tdq_realtime)) != NULL)
899ad1e7d28SJulian Elischer 		return (ts);
900ae7a6b38SJeff Roberson 	if ((ts = runq_steal_from(&tdq->tdq_timeshare, tdq->tdq_ridx)) != NULL)
901ad1e7d28SJulian Elischer 		return (ts);
90280f86c9fSJeff Roberson 	if (stealidle)
903d2ad694cSJeff Roberson 		return (runq_steal(&tdq->tdq_idle));
90480f86c9fSJeff Roberson 	return (NULL);
90522bf7d9aSJeff Roberson }
90680f86c9fSJeff Roberson 
907ae7a6b38SJeff Roberson /*
908ae7a6b38SJeff Roberson  * Sets the thread lock and ts_cpu to match the requested cpu.  Unlocks the
909ae7a6b38SJeff Roberson  * current lock and returns with the assigned queue locked.  If this is
910ae7a6b38SJeff Roberson  * via sched_switch() we leave the thread in a blocked state as an
911ae7a6b38SJeff Roberson  * optimization.
912ae7a6b38SJeff Roberson  */
913ae7a6b38SJeff Roberson static inline struct tdq *
914ae7a6b38SJeff Roberson sched_setcpu(struct td_sched *ts, int cpu, int flags)
91580f86c9fSJeff Roberson {
916ae7a6b38SJeff Roberson 	struct thread *td;
917ae7a6b38SJeff Roberson 	struct tdq *tdq;
91880f86c9fSJeff Roberson 
919ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(ts->ts_thread, MA_OWNED);
920ae7a6b38SJeff Roberson 
921ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpu);
922ae7a6b38SJeff Roberson 	td = ts->ts_thread;
923ae7a6b38SJeff Roberson 	ts->ts_cpu = cpu;
924ae7a6b38SJeff Roberson 	if (td->td_lock == TDQ_LOCKPTR(tdq))
925ae7a6b38SJeff Roberson 		return (tdq);
926ae7a6b38SJeff Roberson #ifdef notyet
92780f86c9fSJeff Roberson 	/*
928ae7a6b38SJeff Roberson 	 * If the thread isn't running it's lockptr is a
929ae7a6b38SJeff Roberson 	 * turnstile or a sleepqueue.  We can just lock_set without
930ae7a6b38SJeff Roberson 	 * blocking.
931670c524fSJeff Roberson 	 */
932ae7a6b38SJeff Roberson 	if (TD_CAN_RUN(td)) {
933ae7a6b38SJeff Roberson 		TDQ_LOCK(tdq);
934ae7a6b38SJeff Roberson 		thread_lock_set(td, TDQ_LOCKPTR(tdq));
935ae7a6b38SJeff Roberson 		return (tdq);
936ae7a6b38SJeff Roberson 	}
937ae7a6b38SJeff Roberson #endif
93880f86c9fSJeff Roberson 	/*
939ae7a6b38SJeff Roberson 	 * The hard case, migration, we need to block the thread first to
940ae7a6b38SJeff Roberson 	 * prevent order reversals with other cpus locks.
9417b8bfa0dSJeff Roberson 	 */
942ae7a6b38SJeff Roberson 	thread_lock_block(td);
943ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
944ae7a6b38SJeff Roberson 	/* Return to sched_switch() with the lock still blocked */
945ae7a6b38SJeff Roberson 	if ((flags & SRQ_OURSELF) == 0)
946ae7a6b38SJeff Roberson 		thread_lock_unblock(td, TDQ_LOCKPTR(tdq));
947ae7a6b38SJeff Roberson 	return (tdq);
94880f86c9fSJeff Roberson }
9492454aaf5SJeff Roberson 
950ae7a6b38SJeff Roberson /*
951ae7a6b38SJeff Roberson  * Find the thread queue running the lowest priority thread.
952ae7a6b38SJeff Roberson  */
9537b8bfa0dSJeff Roberson static int
954ae7a6b38SJeff Roberson tdq_lowestpri(void)
9557b8bfa0dSJeff Roberson {
956ae7a6b38SJeff Roberson 	struct tdq *tdq;
9577b8bfa0dSJeff Roberson 	int lowpri;
9587b8bfa0dSJeff Roberson 	int lowcpu;
9597b8bfa0dSJeff Roberson 	int lowload;
9607b8bfa0dSJeff Roberson 	int load;
961ae7a6b38SJeff Roberson 	int cpu;
962ae7a6b38SJeff Roberson 	int pri;
963ae7a6b38SJeff Roberson 
964ae7a6b38SJeff Roberson 	lowload = 0;
965ae7a6b38SJeff Roberson 	lowpri = lowcpu = 0;
966ae7a6b38SJeff Roberson 	for (cpu = 0; cpu <= mp_maxid; cpu++) {
967ae7a6b38SJeff Roberson 		if (CPU_ABSENT(cpu))
968ae7a6b38SJeff Roberson 			continue;
969ae7a6b38SJeff Roberson 		tdq = TDQ_CPU(cpu);
970ae7a6b38SJeff Roberson 		pri = tdq->tdq_lowpri;
971ae7a6b38SJeff Roberson 		load = TDQ_CPU(cpu)->tdq_load;
972ae7a6b38SJeff Roberson 		CTR4(KTR_ULE,
973ae7a6b38SJeff Roberson 		    "cpu %d pri %d lowcpu %d lowpri %d",
974ae7a6b38SJeff Roberson 		    cpu, pri, lowcpu, lowpri);
975ae7a6b38SJeff Roberson 		if (pri < lowpri)
976ae7a6b38SJeff Roberson 			continue;
977ae7a6b38SJeff Roberson 		if (lowpri && lowpri == pri && load > lowload)
978ae7a6b38SJeff Roberson 			continue;
979ae7a6b38SJeff Roberson 		lowpri = pri;
980ae7a6b38SJeff Roberson 		lowcpu = cpu;
981ae7a6b38SJeff Roberson 		lowload = load;
982ae7a6b38SJeff Roberson 	}
983ae7a6b38SJeff Roberson 
984ae7a6b38SJeff Roberson 	return (lowcpu);
985ae7a6b38SJeff Roberson }
986ae7a6b38SJeff Roberson 
987ae7a6b38SJeff Roberson /*
988ae7a6b38SJeff Roberson  * Find the thread queue with the least load.
989ae7a6b38SJeff Roberson  */
990ae7a6b38SJeff Roberson static int
991ae7a6b38SJeff Roberson tdq_lowestload(void)
992ae7a6b38SJeff Roberson {
993ae7a6b38SJeff Roberson 	struct tdq *tdq;
994ae7a6b38SJeff Roberson 	int lowload;
995ae7a6b38SJeff Roberson 	int lowpri;
996ae7a6b38SJeff Roberson 	int lowcpu;
997ae7a6b38SJeff Roberson 	int load;
998ae7a6b38SJeff Roberson 	int cpu;
999ae7a6b38SJeff Roberson 	int pri;
1000ae7a6b38SJeff Roberson 
1001ae7a6b38SJeff Roberson 	lowcpu = 0;
1002ae7a6b38SJeff Roberson 	lowload = TDQ_CPU(0)->tdq_load;
1003ae7a6b38SJeff Roberson 	lowpri = TDQ_CPU(0)->tdq_lowpri;
1004ae7a6b38SJeff Roberson 	for (cpu = 1; cpu <= mp_maxid; cpu++) {
1005ae7a6b38SJeff Roberson 		if (CPU_ABSENT(cpu))
1006ae7a6b38SJeff Roberson 			continue;
1007ae7a6b38SJeff Roberson 		tdq = TDQ_CPU(cpu);
1008ae7a6b38SJeff Roberson 		load = tdq->tdq_load;
1009ae7a6b38SJeff Roberson 		pri = tdq->tdq_lowpri;
1010ae7a6b38SJeff Roberson 		CTR4(KTR_ULE, "cpu %d load %d lowcpu %d lowload %d",
1011ae7a6b38SJeff Roberson 		    cpu, load, lowcpu, lowload);
1012ae7a6b38SJeff Roberson 		if (load > lowload)
1013ae7a6b38SJeff Roberson 			continue;
1014ae7a6b38SJeff Roberson 		if (load == lowload && pri < lowpri)
1015ae7a6b38SJeff Roberson 			continue;
1016ae7a6b38SJeff Roberson 		lowcpu = cpu;
1017ae7a6b38SJeff Roberson 		lowload = load;
1018ae7a6b38SJeff Roberson 		lowpri = pri;
1019ae7a6b38SJeff Roberson 	}
1020ae7a6b38SJeff Roberson 
1021ae7a6b38SJeff Roberson 	return (lowcpu);
1022ae7a6b38SJeff Roberson }
1023ae7a6b38SJeff Roberson 
1024ae7a6b38SJeff Roberson /*
1025ae7a6b38SJeff Roberson  * Pick the destination cpu for sched_add().  Respects affinity and makes
1026ae7a6b38SJeff Roberson  * a determination based on load or priority of available processors.
1027ae7a6b38SJeff Roberson  */
1028ae7a6b38SJeff Roberson static int
1029ae7a6b38SJeff Roberson sched_pickcpu(struct td_sched *ts, int flags)
1030ae7a6b38SJeff Roberson {
1031ae7a6b38SJeff Roberson 	struct tdq *tdq;
10327b8bfa0dSJeff Roberson 	int self;
10337b8bfa0dSJeff Roberson 	int pri;
10347b8bfa0dSJeff Roberson 	int cpu;
10357b8bfa0dSJeff Roberson 
1036ae7a6b38SJeff Roberson 	cpu = self = PCPU_GET(cpuid);
10377b8bfa0dSJeff Roberson 	if (smp_started == 0)
10387b8bfa0dSJeff Roberson 		return (self);
10397b8bfa0dSJeff Roberson 	pri = ts->ts_thread->td_priority;
1040ae7a6b38SJeff Roberson 	cpu = ts->ts_cpu;
10417b8bfa0dSJeff Roberson 	/*
10427b8bfa0dSJeff Roberson 	 * Regardless of affinity, if the last cpu is idle send it there.
10437b8bfa0dSJeff Roberson 	 */
1044ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpu);
1045ae7a6b38SJeff Roberson 	if (tdq->tdq_lowpri > PRI_MIN_IDLE) {
104614618990SJeff Roberson 		CTR5(KTR_ULE,
10477b8bfa0dSJeff Roberson 		    "ts_cpu %d idle, ltick %d ticks %d pri %d curthread %d",
10487b8bfa0dSJeff Roberson 		    ts->ts_cpu, ts->ts_rltick, ticks, pri,
1049ae7a6b38SJeff Roberson 		    tdq->tdq_lowpri);
10507b8bfa0dSJeff Roberson 		return (ts->ts_cpu);
10517b8bfa0dSJeff Roberson 	}
10527b8bfa0dSJeff Roberson 	/*
10537b8bfa0dSJeff Roberson 	 * If we have affinity, try to place it on the cpu we last ran on.
10547b8bfa0dSJeff Roberson 	 */
1055ae7a6b38SJeff Roberson 	if (SCHED_AFFINITY(ts) && tdq->tdq_lowpri > pri) {
105614618990SJeff Roberson 		CTR5(KTR_ULE,
10577b8bfa0dSJeff Roberson 		    "affinity for %d, ltick %d ticks %d pri %d curthread %d",
10587b8bfa0dSJeff Roberson 		    ts->ts_cpu, ts->ts_rltick, ticks, pri,
1059ae7a6b38SJeff Roberson 		    tdq->tdq_lowpri);
10607b8bfa0dSJeff Roberson 		return (ts->ts_cpu);
10617b8bfa0dSJeff Roberson 	}
10627b8bfa0dSJeff Roberson 	/*
10637b8bfa0dSJeff Roberson 	 * Try ourself first; If we're running something lower priority this
10647b8bfa0dSJeff Roberson 	 * may have some locality with the waking thread and execute faster
10657b8bfa0dSJeff Roberson 	 * here.
10667b8bfa0dSJeff Roberson 	 */
10677b8bfa0dSJeff Roberson 	if (tryself) {
10687b8bfa0dSJeff Roberson 		/*
10697b8bfa0dSJeff Roberson 		 * If we're being awoken by an interrupt thread or the waker
10707b8bfa0dSJeff Roberson 		 * is going right to sleep run here as well.
10717b8bfa0dSJeff Roberson 		 */
1072ae7a6b38SJeff Roberson 		if ((TDQ_SELF()->tdq_load <= 1) && (flags & (SRQ_YIELDING) ||
10737b8bfa0dSJeff Roberson 		    curthread->td_pri_class == PRI_ITHD)) {
107414618990SJeff Roberson 			CTR2(KTR_ULE, "tryself load %d flags %d",
10757b8bfa0dSJeff Roberson 			    TDQ_SELF()->tdq_load, flags);
10767b8bfa0dSJeff Roberson 			return (self);
10777b8bfa0dSJeff Roberson 		}
10787b8bfa0dSJeff Roberson 	}
10797b8bfa0dSJeff Roberson 	/*
10807b8bfa0dSJeff Roberson 	 * Look for an idle group.
10817b8bfa0dSJeff Roberson 	 */
108214618990SJeff Roberson 	CTR1(KTR_ULE, "tdq_idle %X", tdq_idle);
10837b8bfa0dSJeff Roberson 	cpu = ffs(tdq_idle);
10847b8bfa0dSJeff Roberson 	if (cpu)
1085ae7a6b38SJeff Roberson 		return (--cpu);
10867b8bfa0dSJeff Roberson 	if (tryselfidle && pri < curthread->td_priority) {
1087ae7a6b38SJeff Roberson 		CTR1(KTR_ULE, "tryselfidle %d",
10887b8bfa0dSJeff Roberson 		    curthread->td_priority);
10897b8bfa0dSJeff Roberson 		return (self);
10907b8bfa0dSJeff Roberson 	}
10917b8bfa0dSJeff Roberson 	/*
1092ae7a6b38SJeff Roberson 	 * XXX Under heavy load mysql performs way better if you
1093ae7a6b38SJeff Roberson 	 * serialize the non-running threads on one cpu.  This is
1094ae7a6b38SJeff Roberson 	 * a horrible hack.
1095ae7a6b38SJeff Roberson 	 */
1096ae7a6b38SJeff Roberson 	if (pick_zero)
1097ae7a6b38SJeff Roberson 		return (0);
1098ae7a6b38SJeff Roberson 	/*
10997b8bfa0dSJeff Roberson  	 * Now search for the cpu running the lowest priority thread with
11007b8bfa0dSJeff Roberson 	 * the least load.
11017b8bfa0dSJeff Roberson 	 */
1102ae7a6b38SJeff Roberson 	if (pick_pri)
1103ae7a6b38SJeff Roberson 		cpu = tdq_lowestpri();
1104ae7a6b38SJeff Roberson 	else
1105ae7a6b38SJeff Roberson 		cpu = tdq_lowestload();
1106ae7a6b38SJeff Roberson 	return (cpu);
110780f86c9fSJeff Roberson }
110880f86c9fSJeff Roberson 
110922bf7d9aSJeff Roberson #endif	/* SMP */
111022bf7d9aSJeff Roberson 
111122bf7d9aSJeff Roberson /*
111222bf7d9aSJeff Roberson  * Pick the highest priority task we have and return it.
11130c0a98b2SJeff Roberson  */
1114ad1e7d28SJulian Elischer static struct td_sched *
1115ad1e7d28SJulian Elischer tdq_choose(struct tdq *tdq)
11165d7ef00cSJeff Roberson {
1117ad1e7d28SJulian Elischer 	struct td_sched *ts;
11185d7ef00cSJeff Roberson 
1119ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
1120e7d50326SJeff Roberson 	ts = runq_choose(&tdq->tdq_realtime);
1121dda713dfSJeff Roberson 	if (ts != NULL)
1122e7d50326SJeff Roberson 		return (ts);
11233f872f85SJeff Roberson 	ts = runq_choose_from(&tdq->tdq_timeshare, tdq->tdq_ridx);
1124e7d50326SJeff Roberson 	if (ts != NULL) {
1125dda713dfSJeff Roberson 		KASSERT(ts->ts_thread->td_priority >= PRI_MIN_TIMESHARE,
1126e7d50326SJeff Roberson 		    ("tdq_choose: Invalid priority on timeshare queue %d",
1127e7d50326SJeff Roberson 		    ts->ts_thread->td_priority));
1128ad1e7d28SJulian Elischer 		return (ts);
112915dc847eSJeff Roberson 	}
113015dc847eSJeff Roberson 
1131e7d50326SJeff Roberson 	ts = runq_choose(&tdq->tdq_idle);
1132e7d50326SJeff Roberson 	if (ts != NULL) {
1133e7d50326SJeff Roberson 		KASSERT(ts->ts_thread->td_priority >= PRI_MIN_IDLE,
1134e7d50326SJeff Roberson 		    ("tdq_choose: Invalid priority on idle queue %d",
1135e7d50326SJeff Roberson 		    ts->ts_thread->td_priority));
1136e7d50326SJeff Roberson 		return (ts);
1137e7d50326SJeff Roberson 	}
1138e7d50326SJeff Roberson 
1139e7d50326SJeff Roberson 	return (NULL);
1140245f3abfSJeff Roberson }
11410a016a05SJeff Roberson 
1142ae7a6b38SJeff Roberson /*
1143ae7a6b38SJeff Roberson  * Initialize a thread queue.
1144ae7a6b38SJeff Roberson  */
11450a016a05SJeff Roberson static void
1146ad1e7d28SJulian Elischer tdq_setup(struct tdq *tdq)
11470a016a05SJeff Roberson {
1148ae7a6b38SJeff Roberson 
1149ae7a6b38SJeff Roberson 	snprintf(tdq->tdq_name, sizeof(tdq->tdq_name),
1150ae7a6b38SJeff Roberson 	    "sched lock %d", (int)TDQ_ID(tdq));
1151ae7a6b38SJeff Roberson 	mtx_init(&tdq->tdq_lock, tdq->tdq_name, "sched lock",
1152ae7a6b38SJeff Roberson 	    MTX_SPIN | MTX_RECURSE);
1153e7d50326SJeff Roberson 	runq_init(&tdq->tdq_realtime);
1154e7d50326SJeff Roberson 	runq_init(&tdq->tdq_timeshare);
1155d2ad694cSJeff Roberson 	runq_init(&tdq->tdq_idle);
1156d2ad694cSJeff Roberson 	tdq->tdq_load = 0;
11570a016a05SJeff Roberson }
11580a016a05SJeff Roberson 
1159ae7a6b38SJeff Roberson /*
1160ae7a6b38SJeff Roberson  * Setup the thread queues and initialize the topology based on MD
1161ae7a6b38SJeff Roberson  * information.
1162ae7a6b38SJeff Roberson  */
116335e6168fSJeff Roberson static void
116435e6168fSJeff Roberson sched_setup(void *dummy)
116535e6168fSJeff Roberson {
1166ae7a6b38SJeff Roberson 	struct tdq *tdq;
11670ec896fdSJeff Roberson #ifdef SMP
1168ae7a6b38SJeff Roberson 	int balance_groups;
116935e6168fSJeff Roberson 	int i;
117035e6168fSJeff Roberson 
1171cac77d04SJeff Roberson 	balance_groups = 0;
117280f86c9fSJeff Roberson 	/*
1173ad1e7d28SJulian Elischer 	 * Initialize the tdqs.
117480f86c9fSJeff Roberson 	 */
1175749d01b0SJeff Roberson 	for (i = 0; i < MAXCPU; i++) {
1176c02bbb43SJeff Roberson 		tdq = &tdq_cpu[i];
1177ad1e7d28SJulian Elischer 		tdq_setup(&tdq_cpu[i]);
117880f86c9fSJeff Roberson 	}
11797b20fb19SJeff Roberson 	if (smp_topology == NULL) {
1180d2ad694cSJeff Roberson 		struct tdq_group *tdg;
1181598b368dSJeff Roberson 		int cpus;
118280f86c9fSJeff Roberson 
1183598b368dSJeff Roberson 		for (cpus = 0, i = 0; i < MAXCPU; i++) {
1184598b368dSJeff Roberson 			if (CPU_ABSENT(i))
1185598b368dSJeff Roberson 				continue;
1186c02bbb43SJeff Roberson 			tdq = &tdq_cpu[i];
1187d2ad694cSJeff Roberson 			tdg = &tdq_groups[cpus];
118880f86c9fSJeff Roberson 			/*
1189ad1e7d28SJulian Elischer 			 * Setup a tdq group with one member.
119080f86c9fSJeff Roberson 			 */
1191c02bbb43SJeff Roberson 			tdq->tdq_transferable = 0;
1192c02bbb43SJeff Roberson 			tdq->tdq_group = tdg;
1193d2ad694cSJeff Roberson 			tdg->tdg_cpus = 1;
1194d2ad694cSJeff Roberson 			tdg->tdg_idlemask = 0;
1195d2ad694cSJeff Roberson 			tdg->tdg_cpumask = tdg->tdg_mask = 1 << i;
1196d2ad694cSJeff Roberson 			tdg->tdg_load = 0;
1197d2ad694cSJeff Roberson 			tdg->tdg_transferable = 0;
1198d2ad694cSJeff Roberson 			LIST_INIT(&tdg->tdg_members);
1199c02bbb43SJeff Roberson 			LIST_INSERT_HEAD(&tdg->tdg_members, tdq, tdq_siblings);
1200598b368dSJeff Roberson 			cpus++;
1201749d01b0SJeff Roberson 		}
1202d2ad694cSJeff Roberson 		tdg_maxid = cpus - 1;
1203749d01b0SJeff Roberson 	} else {
1204d2ad694cSJeff Roberson 		struct tdq_group *tdg;
120580f86c9fSJeff Roberson 		struct cpu_group *cg;
1206749d01b0SJeff Roberson 		int j;
1207749d01b0SJeff Roberson 
12087b20fb19SJeff Roberson 		topology = 1;
1209749d01b0SJeff Roberson 		for (i = 0; i < smp_topology->ct_count; i++) {
1210749d01b0SJeff Roberson 			cg = &smp_topology->ct_group[i];
1211d2ad694cSJeff Roberson 			tdg = &tdq_groups[i];
121280f86c9fSJeff Roberson 			/*
121380f86c9fSJeff Roberson 			 * Initialize the group.
121480f86c9fSJeff Roberson 			 */
1215d2ad694cSJeff Roberson 			tdg->tdg_idlemask = 0;
1216d2ad694cSJeff Roberson 			tdg->tdg_load = 0;
1217d2ad694cSJeff Roberson 			tdg->tdg_transferable = 0;
1218d2ad694cSJeff Roberson 			tdg->tdg_cpus = cg->cg_count;
1219d2ad694cSJeff Roberson 			tdg->tdg_cpumask = cg->cg_mask;
1220d2ad694cSJeff Roberson 			LIST_INIT(&tdg->tdg_members);
122180f86c9fSJeff Roberson 			/*
122280f86c9fSJeff Roberson 			 * Find all of the group members and add them.
122380f86c9fSJeff Roberson 			 */
122480f86c9fSJeff Roberson 			for (j = 0; j < MAXCPU; j++) {
122580f86c9fSJeff Roberson 				if ((cg->cg_mask & (1 << j)) != 0) {
1226d2ad694cSJeff Roberson 					if (tdg->tdg_mask == 0)
1227d2ad694cSJeff Roberson 						tdg->tdg_mask = 1 << j;
1228d2ad694cSJeff Roberson 					tdq_cpu[j].tdq_transferable = 0;
1229d2ad694cSJeff Roberson 					tdq_cpu[j].tdq_group = tdg;
1230d2ad694cSJeff Roberson 					LIST_INSERT_HEAD(&tdg->tdg_members,
1231d2ad694cSJeff Roberson 					    &tdq_cpu[j], tdq_siblings);
123280f86c9fSJeff Roberson 				}
123380f86c9fSJeff Roberson 			}
1234d2ad694cSJeff Roberson 			if (tdg->tdg_cpus > 1)
1235cac77d04SJeff Roberson 				balance_groups = 1;
1236749d01b0SJeff Roberson 		}
1237d2ad694cSJeff Roberson 		tdg_maxid = smp_topology->ct_count - 1;
1238749d01b0SJeff Roberson 	}
1239cac77d04SJeff Roberson 	/*
1240ae7a6b38SJeff Roberson 	 * Initialize long-term cpu balancing algorithm.
1241cac77d04SJeff Roberson 	 */
1242ae7a6b38SJeff Roberson 	callout_init(&balco, CALLOUT_MPSAFE);
1243ae7a6b38SJeff Roberson 	callout_init(&gbalco, CALLOUT_MPSAFE);
1244ae7a6b38SJeff Roberson 	sched_balance(NULL);
1245cac77d04SJeff Roberson 	if (balance_groups)
1246ae7a6b38SJeff Roberson 		sched_balance_groups(NULL);
1247ae7a6b38SJeff Roberson 
1248749d01b0SJeff Roberson #else
1249ad1e7d28SJulian Elischer 	tdq_setup(TDQ_SELF());
1250356500a3SJeff Roberson #endif
1251ae7a6b38SJeff Roberson 	/*
1252ae7a6b38SJeff Roberson 	 * To avoid divide-by-zero, we set realstathz a dummy value
1253ae7a6b38SJeff Roberson 	 * in case which sched_clock() called before sched_initticks().
1254ae7a6b38SJeff Roberson 	 */
1255ae7a6b38SJeff Roberson 	realstathz = hz;
1256ae7a6b38SJeff Roberson 	sched_slice = (realstathz/10);	/* ~100ms */
1257ae7a6b38SJeff Roberson 	tickincr = 1 << SCHED_TICK_SHIFT;
1258ae7a6b38SJeff Roberson 
1259ae7a6b38SJeff Roberson 	/* Add thread0's load since it's running. */
1260ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
1261ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
1262ae7a6b38SJeff Roberson 	tdq_load_add(tdq, &td_sched0);
1263ae7a6b38SJeff Roberson 	TDQ_UNLOCK(tdq);
126435e6168fSJeff Roberson }
126535e6168fSJeff Roberson 
1266ae7a6b38SJeff Roberson /*
1267ae7a6b38SJeff Roberson  * This routine determines the tickincr after stathz and hz are setup.
1268ae7a6b38SJeff Roberson  */
1269a1d4fe69SDavid Xu /* ARGSUSED */
1270a1d4fe69SDavid Xu static void
1271a1d4fe69SDavid Xu sched_initticks(void *dummy)
1272a1d4fe69SDavid Xu {
1273ae7a6b38SJeff Roberson 	int incr;
1274ae7a6b38SJeff Roberson 
1275a1d4fe69SDavid Xu 	realstathz = stathz ? stathz : hz;
127614618990SJeff Roberson 	sched_slice = (realstathz/10);	/* ~100ms */
1277a1d4fe69SDavid Xu 
1278a1d4fe69SDavid Xu 	/*
1279e7d50326SJeff Roberson 	 * tickincr is shifted out by 10 to avoid rounding errors due to
12803f872f85SJeff Roberson 	 * hz not being evenly divisible by stathz on all platforms.
1281e7d50326SJeff Roberson 	 */
1282ae7a6b38SJeff Roberson 	incr = (hz << SCHED_TICK_SHIFT) / realstathz;
1283e7d50326SJeff Roberson 	/*
1284e7d50326SJeff Roberson 	 * This does not work for values of stathz that are more than
1285e7d50326SJeff Roberson 	 * 1 << SCHED_TICK_SHIFT * hz.  In practice this does not happen.
1286a1d4fe69SDavid Xu 	 */
1287ae7a6b38SJeff Roberson 	if (incr == 0)
1288ae7a6b38SJeff Roberson 		incr = 1;
1289ae7a6b38SJeff Roberson 	tickincr = incr;
12907b8bfa0dSJeff Roberson #ifdef SMP
12917b8bfa0dSJeff Roberson 	affinity = SCHED_AFFINITY_DEFAULT;
12927b8bfa0dSJeff Roberson #endif
1293a1d4fe69SDavid Xu }
1294a1d4fe69SDavid Xu 
1295a1d4fe69SDavid Xu 
129635e6168fSJeff Roberson /*
1297ae7a6b38SJeff Roberson  * This is the core of the interactivity algorithm.  Determines a score based
1298ae7a6b38SJeff Roberson  * on past behavior.  It is the ratio of sleep time to run time scaled to
1299ae7a6b38SJeff Roberson  * a [0, 100] integer.  This is the voluntary sleep time of a process, which
1300ae7a6b38SJeff Roberson  * differs from the cpu usage because it does not account for time spent
1301ae7a6b38SJeff Roberson  * waiting on a run-queue.  Would be prettier if we had floating point.
1302ae7a6b38SJeff Roberson  */
1303ae7a6b38SJeff Roberson static int
1304ae7a6b38SJeff Roberson sched_interact_score(struct thread *td)
1305ae7a6b38SJeff Roberson {
1306ae7a6b38SJeff Roberson 	struct td_sched *ts;
1307ae7a6b38SJeff Roberson 	int div;
1308ae7a6b38SJeff Roberson 
1309ae7a6b38SJeff Roberson 	ts = td->td_sched;
1310ae7a6b38SJeff Roberson 	/*
1311ae7a6b38SJeff Roberson 	 * The score is only needed if this is likely to be an interactive
1312ae7a6b38SJeff Roberson 	 * task.  Don't go through the expense of computing it if there's
1313ae7a6b38SJeff Roberson 	 * no chance.
1314ae7a6b38SJeff Roberson 	 */
1315ae7a6b38SJeff Roberson 	if (sched_interact <= SCHED_INTERACT_HALF &&
1316ae7a6b38SJeff Roberson 		ts->ts_runtime >= ts->ts_slptime)
1317ae7a6b38SJeff Roberson 			return (SCHED_INTERACT_HALF);
1318ae7a6b38SJeff Roberson 
1319ae7a6b38SJeff Roberson 	if (ts->ts_runtime > ts->ts_slptime) {
1320ae7a6b38SJeff Roberson 		div = max(1, ts->ts_runtime / SCHED_INTERACT_HALF);
1321ae7a6b38SJeff Roberson 		return (SCHED_INTERACT_HALF +
1322ae7a6b38SJeff Roberson 		    (SCHED_INTERACT_HALF - (ts->ts_slptime / div)));
1323ae7a6b38SJeff Roberson 	}
1324ae7a6b38SJeff Roberson 	if (ts->ts_slptime > ts->ts_runtime) {
1325ae7a6b38SJeff Roberson 		div = max(1, ts->ts_slptime / SCHED_INTERACT_HALF);
1326ae7a6b38SJeff Roberson 		return (ts->ts_runtime / div);
1327ae7a6b38SJeff Roberson 	}
1328ae7a6b38SJeff Roberson 	/* runtime == slptime */
1329ae7a6b38SJeff Roberson 	if (ts->ts_runtime)
1330ae7a6b38SJeff Roberson 		return (SCHED_INTERACT_HALF);
1331ae7a6b38SJeff Roberson 
1332ae7a6b38SJeff Roberson 	/*
1333ae7a6b38SJeff Roberson 	 * This can happen if slptime and runtime are 0.
1334ae7a6b38SJeff Roberson 	 */
1335ae7a6b38SJeff Roberson 	return (0);
1336ae7a6b38SJeff Roberson 
1337ae7a6b38SJeff Roberson }
1338ae7a6b38SJeff Roberson 
1339ae7a6b38SJeff Roberson /*
134035e6168fSJeff Roberson  * Scale the scheduling priority according to the "interactivity" of this
134135e6168fSJeff Roberson  * process.
134235e6168fSJeff Roberson  */
134315dc847eSJeff Roberson static void
13448460a577SJohn Birrell sched_priority(struct thread *td)
134535e6168fSJeff Roberson {
1346e7d50326SJeff Roberson 	int score;
134735e6168fSJeff Roberson 	int pri;
134835e6168fSJeff Roberson 
13498460a577SJohn Birrell 	if (td->td_pri_class != PRI_TIMESHARE)
135015dc847eSJeff Roberson 		return;
1351e7d50326SJeff Roberson 	/*
1352e7d50326SJeff Roberson 	 * If the score is interactive we place the thread in the realtime
1353e7d50326SJeff Roberson 	 * queue with a priority that is less than kernel and interrupt
1354e7d50326SJeff Roberson 	 * priorities.  These threads are not subject to nice restrictions.
1355e7d50326SJeff Roberson 	 *
1356ae7a6b38SJeff Roberson 	 * Scores greater than this are placed on the normal timeshare queue
1357e7d50326SJeff Roberson 	 * where the priority is partially decided by the most recent cpu
1358e7d50326SJeff Roberson 	 * utilization and the rest is decided by nice value.
1359e7d50326SJeff Roberson 	 */
1360e7d50326SJeff Roberson 	score = sched_interact_score(td);
1361e7d50326SJeff Roberson 	if (score < sched_interact) {
1362e7d50326SJeff Roberson 		pri = PRI_MIN_REALTIME;
1363e7d50326SJeff Roberson 		pri += ((PRI_MAX_REALTIME - PRI_MIN_REALTIME) / sched_interact)
1364e7d50326SJeff Roberson 		    * score;
1365e7d50326SJeff Roberson 		KASSERT(pri >= PRI_MIN_REALTIME && pri <= PRI_MAX_REALTIME,
13669a93305aSJeff Roberson 		    ("sched_priority: invalid interactive priority %d score %d",
13679a93305aSJeff Roberson 		    pri, score));
1368e7d50326SJeff Roberson 	} else {
1369e7d50326SJeff Roberson 		pri = SCHED_PRI_MIN;
1370e7d50326SJeff Roberson 		if (td->td_sched->ts_ticks)
1371e7d50326SJeff Roberson 			pri += SCHED_PRI_TICKS(td->td_sched);
1372e7d50326SJeff Roberson 		pri += SCHED_PRI_NICE(td->td_proc->p_nice);
1373ae7a6b38SJeff Roberson 		KASSERT(pri >= PRI_MIN_TIMESHARE && pri <= PRI_MAX_TIMESHARE,
1374ae7a6b38SJeff Roberson 		    ("sched_priority: invalid priority %d: nice %d, "
1375ae7a6b38SJeff Roberson 		    "ticks %d ftick %d ltick %d tick pri %d",
1376ae7a6b38SJeff Roberson 		    pri, td->td_proc->p_nice, td->td_sched->ts_ticks,
1377ae7a6b38SJeff Roberson 		    td->td_sched->ts_ftick, td->td_sched->ts_ltick,
1378ae7a6b38SJeff Roberson 		    SCHED_PRI_TICKS(td->td_sched)));
1379e7d50326SJeff Roberson 	}
13808460a577SJohn Birrell 	sched_user_prio(td, pri);
138135e6168fSJeff Roberson 
138215dc847eSJeff Roberson 	return;
138335e6168fSJeff Roberson }
138435e6168fSJeff Roberson 
138535e6168fSJeff Roberson /*
1386d322132cSJeff Roberson  * This routine enforces a maximum limit on the amount of scheduling history
1387ae7a6b38SJeff Roberson  * kept.  It is called after either the slptime or runtime is adjusted.  This
1388ae7a6b38SJeff Roberson  * function is ugly due to integer math.
1389d322132cSJeff Roberson  */
13904b60e324SJeff Roberson static void
13918460a577SJohn Birrell sched_interact_update(struct thread *td)
13924b60e324SJeff Roberson {
1393155b6ca1SJeff Roberson 	struct td_sched *ts;
13949a93305aSJeff Roberson 	u_int sum;
13953f741ca1SJeff Roberson 
1396155b6ca1SJeff Roberson 	ts = td->td_sched;
1397ae7a6b38SJeff Roberson 	sum = ts->ts_runtime + ts->ts_slptime;
1398d322132cSJeff Roberson 	if (sum < SCHED_SLP_RUN_MAX)
1399d322132cSJeff Roberson 		return;
1400d322132cSJeff Roberson 	/*
1401155b6ca1SJeff Roberson 	 * This only happens from two places:
1402155b6ca1SJeff Roberson 	 * 1) We have added an unusual amount of run time from fork_exit.
1403155b6ca1SJeff Roberson 	 * 2) We have added an unusual amount of sleep time from sched_sleep().
1404155b6ca1SJeff Roberson 	 */
1405155b6ca1SJeff Roberson 	if (sum > SCHED_SLP_RUN_MAX * 2) {
1406ae7a6b38SJeff Roberson 		if (ts->ts_runtime > ts->ts_slptime) {
1407ae7a6b38SJeff Roberson 			ts->ts_runtime = SCHED_SLP_RUN_MAX;
1408ae7a6b38SJeff Roberson 			ts->ts_slptime = 1;
1409155b6ca1SJeff Roberson 		} else {
1410ae7a6b38SJeff Roberson 			ts->ts_slptime = SCHED_SLP_RUN_MAX;
1411ae7a6b38SJeff Roberson 			ts->ts_runtime = 1;
1412155b6ca1SJeff Roberson 		}
1413155b6ca1SJeff Roberson 		return;
1414155b6ca1SJeff Roberson 	}
1415155b6ca1SJeff Roberson 	/*
1416d322132cSJeff Roberson 	 * If we have exceeded by more than 1/5th then the algorithm below
1417d322132cSJeff Roberson 	 * will not bring us back into range.  Dividing by two here forces
14182454aaf5SJeff Roberson 	 * us into the range of [4/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX]
1419d322132cSJeff Roberson 	 */
142037a35e4aSJeff Roberson 	if (sum > (SCHED_SLP_RUN_MAX / 5) * 6) {
1421ae7a6b38SJeff Roberson 		ts->ts_runtime /= 2;
1422ae7a6b38SJeff Roberson 		ts->ts_slptime /= 2;
1423d322132cSJeff Roberson 		return;
1424d322132cSJeff Roberson 	}
1425ae7a6b38SJeff Roberson 	ts->ts_runtime = (ts->ts_runtime / 5) * 4;
1426ae7a6b38SJeff Roberson 	ts->ts_slptime = (ts->ts_slptime / 5) * 4;
1427d322132cSJeff Roberson }
1428d322132cSJeff Roberson 
1429ae7a6b38SJeff Roberson /*
1430ae7a6b38SJeff Roberson  * Scale back the interactivity history when a child thread is created.  The
1431ae7a6b38SJeff Roberson  * history is inherited from the parent but the thread may behave totally
1432ae7a6b38SJeff Roberson  * differently.  For example, a shell spawning a compiler process.  We want
1433ae7a6b38SJeff Roberson  * to learn that the compiler is behaving badly very quickly.
1434ae7a6b38SJeff Roberson  */
1435d322132cSJeff Roberson static void
14368460a577SJohn Birrell sched_interact_fork(struct thread *td)
1437d322132cSJeff Roberson {
1438d322132cSJeff Roberson 	int ratio;
1439d322132cSJeff Roberson 	int sum;
1440d322132cSJeff Roberson 
1441ae7a6b38SJeff Roberson 	sum = td->td_sched->ts_runtime + td->td_sched->ts_slptime;
1442d322132cSJeff Roberson 	if (sum > SCHED_SLP_RUN_FORK) {
1443d322132cSJeff Roberson 		ratio = sum / SCHED_SLP_RUN_FORK;
1444ae7a6b38SJeff Roberson 		td->td_sched->ts_runtime /= ratio;
1445ae7a6b38SJeff Roberson 		td->td_sched->ts_slptime /= ratio;
14464b60e324SJeff Roberson 	}
14474b60e324SJeff Roberson }
14484b60e324SJeff Roberson 
144915dc847eSJeff Roberson /*
1450ae7a6b38SJeff Roberson  * Called from proc0_init() to setup the scheduler fields.
1451ed062c8dSJulian Elischer  */
1452ed062c8dSJulian Elischer void
1453ed062c8dSJulian Elischer schedinit(void)
1454ed062c8dSJulian Elischer {
1455e7d50326SJeff Roberson 
1456ed062c8dSJulian Elischer 	/*
1457ed062c8dSJulian Elischer 	 * Set up the scheduler specific parts of proc0.
1458ed062c8dSJulian Elischer 	 */
1459ed062c8dSJulian Elischer 	proc0.p_sched = NULL; /* XXX */
1460ad1e7d28SJulian Elischer 	thread0.td_sched = &td_sched0;
1461ae7a6b38SJeff Roberson 	thread0.td_lock = TDQ_LOCKPTR(TDQ_SELF());
1462e7d50326SJeff Roberson 	td_sched0.ts_ltick = ticks;
14638ab80cf0SJeff Roberson 	td_sched0.ts_ftick = ticks;
1464ad1e7d28SJulian Elischer 	td_sched0.ts_thread = &thread0;
1465ed062c8dSJulian Elischer }
1466ed062c8dSJulian Elischer 
1467ed062c8dSJulian Elischer /*
146815dc847eSJeff Roberson  * This is only somewhat accurate since given many processes of the same
146915dc847eSJeff Roberson  * priority they will switch when their slices run out, which will be
1470e7d50326SJeff Roberson  * at most sched_slice stathz ticks.
147115dc847eSJeff Roberson  */
147235e6168fSJeff Roberson int
147335e6168fSJeff Roberson sched_rr_interval(void)
147435e6168fSJeff Roberson {
1475e7d50326SJeff Roberson 
1476e7d50326SJeff Roberson 	/* Convert sched_slice to hz */
1477e7d50326SJeff Roberson 	return (hz/(realstathz/sched_slice));
147835e6168fSJeff Roberson }
147935e6168fSJeff Roberson 
1480ae7a6b38SJeff Roberson /*
1481ae7a6b38SJeff Roberson  * Update the percent cpu tracking information when it is requested or
1482ae7a6b38SJeff Roberson  * the total history exceeds the maximum.  We keep a sliding history of
1483ae7a6b38SJeff Roberson  * tick counts that slowly decays.  This is less precise than the 4BSD
1484ae7a6b38SJeff Roberson  * mechanism since it happens with less regular and frequent events.
1485ae7a6b38SJeff Roberson  */
148622bf7d9aSJeff Roberson static void
1487ad1e7d28SJulian Elischer sched_pctcpu_update(struct td_sched *ts)
148835e6168fSJeff Roberson {
1489e7d50326SJeff Roberson 
1490e7d50326SJeff Roberson 	if (ts->ts_ticks == 0)
1491e7d50326SJeff Roberson 		return;
14928ab80cf0SJeff Roberson 	if (ticks - (hz / 10) < ts->ts_ltick &&
14938ab80cf0SJeff Roberson 	    SCHED_TICK_TOTAL(ts) < SCHED_TICK_MAX)
14948ab80cf0SJeff Roberson 		return;
149535e6168fSJeff Roberson 	/*
149635e6168fSJeff Roberson 	 * Adjust counters and watermark for pctcpu calc.
1497210491d3SJeff Roberson 	 */
1498e7d50326SJeff Roberson 	if (ts->ts_ltick > ticks - SCHED_TICK_TARG)
1499ad1e7d28SJulian Elischer 		ts->ts_ticks = (ts->ts_ticks / (ticks - ts->ts_ftick)) *
1500e7d50326SJeff Roberson 			    SCHED_TICK_TARG;
1501e7d50326SJeff Roberson 	else
1502ad1e7d28SJulian Elischer 		ts->ts_ticks = 0;
1503ad1e7d28SJulian Elischer 	ts->ts_ltick = ticks;
1504e7d50326SJeff Roberson 	ts->ts_ftick = ts->ts_ltick - SCHED_TICK_TARG;
150535e6168fSJeff Roberson }
150635e6168fSJeff Roberson 
1507ae7a6b38SJeff Roberson /*
1508ae7a6b38SJeff Roberson  * Adjust the priority of a thread.  Move it to the appropriate run-queue
1509ae7a6b38SJeff Roberson  * if necessary.  This is the back-end for several priority related
1510ae7a6b38SJeff Roberson  * functions.
1511ae7a6b38SJeff Roberson  */
1512e7d50326SJeff Roberson static void
1513f5c157d9SJohn Baldwin sched_thread_priority(struct thread *td, u_char prio)
151435e6168fSJeff Roberson {
1515ad1e7d28SJulian Elischer 	struct td_sched *ts;
151635e6168fSJeff Roberson 
151781d47d3fSJeff Roberson 	CTR6(KTR_SCHED, "sched_prio: %p(%s) prio %d newprio %d by %p(%s)",
151881d47d3fSJeff Roberson 	    td, td->td_proc->p_comm, td->td_priority, prio, curthread,
151981d47d3fSJeff Roberson 	    curthread->td_proc->p_comm);
1520ad1e7d28SJulian Elischer 	ts = td->td_sched;
15217b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1522f5c157d9SJohn Baldwin 	if (td->td_priority == prio)
1523f5c157d9SJohn Baldwin 		return;
1524e7d50326SJeff Roberson 
15253f872f85SJeff Roberson 	if (TD_ON_RUNQ(td) && prio < td->td_priority) {
15263f741ca1SJeff Roberson 		/*
15273f741ca1SJeff Roberson 		 * If the priority has been elevated due to priority
15283f741ca1SJeff Roberson 		 * propagation, we may have to move ourselves to a new
1529e7d50326SJeff Roberson 		 * queue.  This could be optimized to not re-add in some
1530e7d50326SJeff Roberson 		 * cases.
1531f2b74cbfSJeff Roberson 		 */
1532e7d50326SJeff Roberson 		sched_rem(td);
1533e7d50326SJeff Roberson 		td->td_priority = prio;
1534ae7a6b38SJeff Roberson 		sched_add(td, SRQ_BORROWING);
1535ae7a6b38SJeff Roberson 	} else {
1536ae7a6b38SJeff Roberson #ifdef SMP
1537ae7a6b38SJeff Roberson 		struct tdq *tdq;
1538ae7a6b38SJeff Roberson 
1539ae7a6b38SJeff Roberson 		tdq = TDQ_CPU(ts->ts_cpu);
1540ae7a6b38SJeff Roberson 		if (prio < tdq->tdq_lowpri)
1541ae7a6b38SJeff Roberson 			tdq->tdq_lowpri = prio;
1542ae7a6b38SJeff Roberson #endif
15433f741ca1SJeff Roberson 		td->td_priority = prio;
154435e6168fSJeff Roberson 	}
1545ae7a6b38SJeff Roberson }
154635e6168fSJeff Roberson 
1547f5c157d9SJohn Baldwin /*
1548f5c157d9SJohn Baldwin  * Update a thread's priority when it is lent another thread's
1549f5c157d9SJohn Baldwin  * priority.
1550f5c157d9SJohn Baldwin  */
1551f5c157d9SJohn Baldwin void
1552f5c157d9SJohn Baldwin sched_lend_prio(struct thread *td, u_char prio)
1553f5c157d9SJohn Baldwin {
1554f5c157d9SJohn Baldwin 
1555f5c157d9SJohn Baldwin 	td->td_flags |= TDF_BORROWING;
1556f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1557f5c157d9SJohn Baldwin }
1558f5c157d9SJohn Baldwin 
1559f5c157d9SJohn Baldwin /*
1560f5c157d9SJohn Baldwin  * Restore a thread's priority when priority propagation is
1561f5c157d9SJohn Baldwin  * over.  The prio argument is the minimum priority the thread
1562f5c157d9SJohn Baldwin  * needs to have to satisfy other possible priority lending
1563f5c157d9SJohn Baldwin  * requests.  If the thread's regular priority is less
1564f5c157d9SJohn Baldwin  * important than prio, the thread will keep a priority boost
1565f5c157d9SJohn Baldwin  * of prio.
1566f5c157d9SJohn Baldwin  */
1567f5c157d9SJohn Baldwin void
1568f5c157d9SJohn Baldwin sched_unlend_prio(struct thread *td, u_char prio)
1569f5c157d9SJohn Baldwin {
1570f5c157d9SJohn Baldwin 	u_char base_pri;
1571f5c157d9SJohn Baldwin 
1572f5c157d9SJohn Baldwin 	if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
1573f5c157d9SJohn Baldwin 	    td->td_base_pri <= PRI_MAX_TIMESHARE)
15748460a577SJohn Birrell 		base_pri = td->td_user_pri;
1575f5c157d9SJohn Baldwin 	else
1576f5c157d9SJohn Baldwin 		base_pri = td->td_base_pri;
1577f5c157d9SJohn Baldwin 	if (prio >= base_pri) {
1578f5c157d9SJohn Baldwin 		td->td_flags &= ~TDF_BORROWING;
1579f5c157d9SJohn Baldwin 		sched_thread_priority(td, base_pri);
1580f5c157d9SJohn Baldwin 	} else
1581f5c157d9SJohn Baldwin 		sched_lend_prio(td, prio);
1582f5c157d9SJohn Baldwin }
1583f5c157d9SJohn Baldwin 
1584ae7a6b38SJeff Roberson /*
1585ae7a6b38SJeff Roberson  * Standard entry for setting the priority to an absolute value.
1586ae7a6b38SJeff Roberson  */
1587f5c157d9SJohn Baldwin void
1588f5c157d9SJohn Baldwin sched_prio(struct thread *td, u_char prio)
1589f5c157d9SJohn Baldwin {
1590f5c157d9SJohn Baldwin 	u_char oldprio;
1591f5c157d9SJohn Baldwin 
1592f5c157d9SJohn Baldwin 	/* First, update the base priority. */
1593f5c157d9SJohn Baldwin 	td->td_base_pri = prio;
1594f5c157d9SJohn Baldwin 
1595f5c157d9SJohn Baldwin 	/*
159650aaa791SJohn Baldwin 	 * If the thread is borrowing another thread's priority, don't
1597f5c157d9SJohn Baldwin 	 * ever lower the priority.
1598f5c157d9SJohn Baldwin 	 */
1599f5c157d9SJohn Baldwin 	if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
1600f5c157d9SJohn Baldwin 		return;
1601f5c157d9SJohn Baldwin 
1602f5c157d9SJohn Baldwin 	/* Change the real priority. */
1603f5c157d9SJohn Baldwin 	oldprio = td->td_priority;
1604f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1605f5c157d9SJohn Baldwin 
1606f5c157d9SJohn Baldwin 	/*
1607f5c157d9SJohn Baldwin 	 * If the thread is on a turnstile, then let the turnstile update
1608f5c157d9SJohn Baldwin 	 * its state.
1609f5c157d9SJohn Baldwin 	 */
1610f5c157d9SJohn Baldwin 	if (TD_ON_LOCK(td) && oldprio != prio)
1611f5c157d9SJohn Baldwin 		turnstile_adjust(td, oldprio);
1612f5c157d9SJohn Baldwin }
1613f5c157d9SJohn Baldwin 
1614ae7a6b38SJeff Roberson /*
1615ae7a6b38SJeff Roberson  * Set the base user priority, does not effect current running priority.
1616ae7a6b38SJeff Roberson  */
161735e6168fSJeff Roberson void
16188460a577SJohn Birrell sched_user_prio(struct thread *td, u_char prio)
16193db720fdSDavid Xu {
16203db720fdSDavid Xu 	u_char oldprio;
16213db720fdSDavid Xu 
16228460a577SJohn Birrell 	td->td_base_user_pri = prio;
1623fc6c30f6SJulian Elischer 	if (td->td_flags & TDF_UBORROWING && td->td_user_pri <= prio)
1624fc6c30f6SJulian Elischer                 return;
16258460a577SJohn Birrell 	oldprio = td->td_user_pri;
16268460a577SJohn Birrell 	td->td_user_pri = prio;
16273db720fdSDavid Xu 
16283db720fdSDavid Xu 	if (TD_ON_UPILOCK(td) && oldprio != prio)
16293db720fdSDavid Xu 		umtx_pi_adjust(td, oldprio);
16303db720fdSDavid Xu }
16313db720fdSDavid Xu 
16323db720fdSDavid Xu void
16333db720fdSDavid Xu sched_lend_user_prio(struct thread *td, u_char prio)
16343db720fdSDavid Xu {
16353db720fdSDavid Xu 	u_char oldprio;
16363db720fdSDavid Xu 
16373db720fdSDavid Xu 	td->td_flags |= TDF_UBORROWING;
16383db720fdSDavid Xu 
1639f645b5daSMaxim Konovalov 	oldprio = td->td_user_pri;
16408460a577SJohn Birrell 	td->td_user_pri = prio;
16413db720fdSDavid Xu 
16423db720fdSDavid Xu 	if (TD_ON_UPILOCK(td) && oldprio != prio)
16433db720fdSDavid Xu 		umtx_pi_adjust(td, oldprio);
16443db720fdSDavid Xu }
16453db720fdSDavid Xu 
16463db720fdSDavid Xu void
16473db720fdSDavid Xu sched_unlend_user_prio(struct thread *td, u_char prio)
16483db720fdSDavid Xu {
16493db720fdSDavid Xu 	u_char base_pri;
16503db720fdSDavid Xu 
16518460a577SJohn Birrell 	base_pri = td->td_base_user_pri;
16523db720fdSDavid Xu 	if (prio >= base_pri) {
16533db720fdSDavid Xu 		td->td_flags &= ~TDF_UBORROWING;
16548460a577SJohn Birrell 		sched_user_prio(td, base_pri);
16553db720fdSDavid Xu 	} else
16563db720fdSDavid Xu 		sched_lend_user_prio(td, prio);
16573db720fdSDavid Xu }
16583db720fdSDavid Xu 
1659ae7a6b38SJeff Roberson /*
1660ae7a6b38SJeff Roberson  * Block a thread for switching.  Similar to thread_block() but does not
1661ae7a6b38SJeff Roberson  * bump the spin count.
1662ae7a6b38SJeff Roberson  */
1663ae7a6b38SJeff Roberson static inline struct mtx *
1664ae7a6b38SJeff Roberson thread_block_switch(struct thread *td)
1665ae7a6b38SJeff Roberson {
1666ae7a6b38SJeff Roberson 	struct mtx *lock;
1667ae7a6b38SJeff Roberson 
1668ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1669ae7a6b38SJeff Roberson 	lock = td->td_lock;
1670ae7a6b38SJeff Roberson 	td->td_lock = &blocked_lock;
1671ae7a6b38SJeff Roberson 	mtx_unlock_spin(lock);
1672ae7a6b38SJeff Roberson 
1673ae7a6b38SJeff Roberson 	return (lock);
1674ae7a6b38SJeff Roberson }
1675ae7a6b38SJeff Roberson 
1676ae7a6b38SJeff Roberson /*
1677ae7a6b38SJeff Roberson  * Release a thread that was blocked with thread_block_switch().
1678ae7a6b38SJeff Roberson  */
1679ae7a6b38SJeff Roberson static inline void
1680ae7a6b38SJeff Roberson thread_unblock_switch(struct thread *td, struct mtx *mtx)
1681ae7a6b38SJeff Roberson {
1682ae7a6b38SJeff Roberson 	atomic_store_rel_ptr((volatile uintptr_t *)&td->td_lock,
1683ae7a6b38SJeff Roberson 	    (uintptr_t)mtx);
1684ae7a6b38SJeff Roberson }
1685ae7a6b38SJeff Roberson 
1686ae7a6b38SJeff Roberson /*
1687ae7a6b38SJeff Roberson  * Switch threads.  This function has to handle threads coming in while
1688ae7a6b38SJeff Roberson  * blocked for some reason, running, or idle.  It also must deal with
1689ae7a6b38SJeff Roberson  * migrating a thread from one queue to another as running threads may
1690ae7a6b38SJeff Roberson  * be assigned elsewhere via binding.
1691ae7a6b38SJeff Roberson  */
16923db720fdSDavid Xu void
16933389af30SJulian Elischer sched_switch(struct thread *td, struct thread *newtd, int flags)
169435e6168fSJeff Roberson {
1695c02bbb43SJeff Roberson 	struct tdq *tdq;
1696ad1e7d28SJulian Elischer 	struct td_sched *ts;
1697ae7a6b38SJeff Roberson 	struct mtx *mtx;
1698ae7a6b38SJeff Roberson 	int cpuid;
169935e6168fSJeff Roberson 
17007b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
170135e6168fSJeff Roberson 
1702ae7a6b38SJeff Roberson 	cpuid = PCPU_GET(cpuid);
1703ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpuid);
1704e7d50326SJeff Roberson 	ts = td->td_sched;
1705ae7a6b38SJeff Roberson 	mtx = TDQ_LOCKPTR(tdq);
1706ae7a6b38SJeff Roberson #ifdef SMP
1707ae7a6b38SJeff Roberson 	ts->ts_rltick = ticks;
1708ae7a6b38SJeff Roberson 	if (newtd && newtd->td_priority < tdq->tdq_lowpri)
1709ae7a6b38SJeff Roberson 		tdq->tdq_lowpri = newtd->td_priority;
1710ae7a6b38SJeff Roberson #endif
1711060563ecSJulian Elischer 	td->td_lastcpu = td->td_oncpu;
1712060563ecSJulian Elischer 	td->td_oncpu = NOCPU;
171352eb8464SJohn Baldwin 	td->td_flags &= ~TDF_NEEDRESCHED;
171477918643SStephan Uphoff 	td->td_owepreempt = 0;
1715b11fdad0SJeff Roberson 	/*
1716ae7a6b38SJeff Roberson 	 * The lock pointer in an idle thread should never change.  Reset it
1717ae7a6b38SJeff Roberson 	 * to CAN_RUN as well.
1718b11fdad0SJeff Roberson 	 */
1719486a9414SJulian Elischer 	if (TD_IS_IDLETHREAD(td)) {
1720ae7a6b38SJeff Roberson 		MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1721bf0acc27SJohn Baldwin 		TD_SET_CAN_RUN(td);
17227b20fb19SJeff Roberson 	} else if (TD_IS_RUNNING(td)) {
1723ae7a6b38SJeff Roberson 		MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1724ae7a6b38SJeff Roberson 		/* Remove our load so the selection algorithm is not biased. */
17257b20fb19SJeff Roberson 		tdq_load_rem(tdq, ts);
1726ae7a6b38SJeff Roberson 		sched_add(td, (flags & SW_PREEMPT) ?
1727598b368dSJeff Roberson 		    SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
1728598b368dSJeff Roberson 		    SRQ_OURSELF|SRQ_YIELDING);
1729c20c691bSJulian Elischer 		/*
1730ae7a6b38SJeff Roberson 		 * When migrating we return from sched_add with an extra
1731ae7a6b38SJeff Roberson 		 * spinlock nesting, the tdq locked, and a blocked thread.
1732ae7a6b38SJeff Roberson 		 * This is to optimize out an extra block/unblock cycle here.
1733c20c691bSJulian Elischer 		 */
1734ae7a6b38SJeff Roberson 		if (ts->ts_cpu != cpuid) {
1735ae7a6b38SJeff Roberson 			mtx = TDQ_LOCKPTR(TDQ_CPU(ts->ts_cpu));
1736ae7a6b38SJeff Roberson 			mtx_unlock_spin(mtx);
1737ae7a6b38SJeff Roberson 			TDQ_LOCK(tdq);
1738ae7a6b38SJeff Roberson 			spinlock_exit();
1739ae7a6b38SJeff Roberson 		}
1740ae7a6b38SJeff Roberson 	} else {
1741ae7a6b38SJeff Roberson 		/* This thread must be going to sleep. */
1742ae7a6b38SJeff Roberson 		TDQ_LOCK(tdq);
1743ae7a6b38SJeff Roberson 		mtx = thread_block_switch(td);
1744ae7a6b38SJeff Roberson 		tdq_load_rem(tdq, ts);
1745ae7a6b38SJeff Roberson 	}
1746ae7a6b38SJeff Roberson 	/*
1747ae7a6b38SJeff Roberson 	 * We enter here with the thread blocked and assigned to the
1748ae7a6b38SJeff Roberson 	 * appropriate cpu run-queue or sleep-queue and with the current
1749ae7a6b38SJeff Roberson 	 * thread-queue locked.
1750ae7a6b38SJeff Roberson 	 */
1751ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED | MA_NOTRECURSED);
1752ae7a6b38SJeff Roberson 	/*
1753ae7a6b38SJeff Roberson 	 * If KSE assigned a new thread just add it here and pick the best one.
1754ae7a6b38SJeff Roberson 	 */
1755ae7a6b38SJeff Roberson 	if (newtd != NULL) {
1756ae7a6b38SJeff Roberson 		/* XXX This is bogus.  What if the thread is locked elsewhere? */
1757ae7a6b38SJeff Roberson 		td->td_lock = TDQ_LOCKPTR(tdq);
1758ae7a6b38SJeff Roberson 		td->td_sched->ts_cpu = cpuid;
1759ae7a6b38SJeff Roberson 		tdq_add(tdq, td, SRQ_YIELDING);
1760ae7a6b38SJeff Roberson 	}
17612454aaf5SJeff Roberson 	newtd = choosethread();
1762ae7a6b38SJeff Roberson 	/*
1763ae7a6b38SJeff Roberson 	 * Call the MD code to switch contexts if necessary.
1764ae7a6b38SJeff Roberson 	 */
1765ebccf1e3SJoseph Koshy 	if (td != newtd) {
1766ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
1767ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1768ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
1769ebccf1e3SJoseph Koshy #endif
1770ae7a6b38SJeff Roberson 		cpu_switch(td, newtd, mtx);
1771ae7a6b38SJeff Roberson 		/*
1772ae7a6b38SJeff Roberson 		 * We may return from cpu_switch on a different cpu.  However,
1773ae7a6b38SJeff Roberson 		 * we always return with td_lock pointing to the current cpu's
1774ae7a6b38SJeff Roberson 		 * run queue lock.
1775ae7a6b38SJeff Roberson 		 */
1776ae7a6b38SJeff Roberson 		cpuid = PCPU_GET(cpuid);
1777ae7a6b38SJeff Roberson 		tdq = TDQ_CPU(cpuid);
1778ae7a6b38SJeff Roberson 		TDQ_LOCKPTR(tdq)->mtx_lock = (uintptr_t)td;
1779ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
1780ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1781ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
1782ebccf1e3SJoseph Koshy #endif
1783ae7a6b38SJeff Roberson 	} else
1784ae7a6b38SJeff Roberson 		thread_unblock_switch(td, mtx);
1785ae7a6b38SJeff Roberson 	/*
1786ae7a6b38SJeff Roberson 	 * Assert that all went well and return.
1787ae7a6b38SJeff Roberson 	 */
1788ae7a6b38SJeff Roberson #ifdef SMP
1789ae7a6b38SJeff Roberson 	/* We should always get here with the lowest priority td possible */
1790ae7a6b38SJeff Roberson 	tdq->tdq_lowpri = td->td_priority;
1791ae7a6b38SJeff Roberson #endif
1792ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED|MA_NOTRECURSED);
1793ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1794ae7a6b38SJeff Roberson 	td->td_oncpu = cpuid;
179535e6168fSJeff Roberson }
179635e6168fSJeff Roberson 
1797ae7a6b38SJeff Roberson /*
1798ae7a6b38SJeff Roberson  * Adjust thread priorities as a result of a nice request.
1799ae7a6b38SJeff Roberson  */
180035e6168fSJeff Roberson void
1801fa885116SJulian Elischer sched_nice(struct proc *p, int nice)
180235e6168fSJeff Roberson {
180335e6168fSJeff Roberson 	struct thread *td;
180435e6168fSJeff Roberson 
1805fa885116SJulian Elischer 	PROC_LOCK_ASSERT(p, MA_OWNED);
18067b20fb19SJeff Roberson 	PROC_SLOCK_ASSERT(p, MA_OWNED);
1807e7d50326SJeff Roberson 
1808fa885116SJulian Elischer 	p->p_nice = nice;
18098460a577SJohn Birrell 	FOREACH_THREAD_IN_PROC(p, td) {
18107b20fb19SJeff Roberson 		thread_lock(td);
18118460a577SJohn Birrell 		sched_priority(td);
1812e7d50326SJeff Roberson 		sched_prio(td, td->td_base_user_pri);
18137b20fb19SJeff Roberson 		thread_unlock(td);
181435e6168fSJeff Roberson 	}
1815fa885116SJulian Elischer }
181635e6168fSJeff Roberson 
1817ae7a6b38SJeff Roberson /*
1818ae7a6b38SJeff Roberson  * Record the sleep time for the interactivity scorer.
1819ae7a6b38SJeff Roberson  */
182035e6168fSJeff Roberson void
182144f3b092SJohn Baldwin sched_sleep(struct thread *td)
182235e6168fSJeff Roberson {
1823e7d50326SJeff Roberson 
18247b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
182535e6168fSJeff Roberson 
1826ae7a6b38SJeff Roberson 	td->td_sched->ts_slptick = ticks;
182735e6168fSJeff Roberson }
182835e6168fSJeff Roberson 
1829ae7a6b38SJeff Roberson /*
1830ae7a6b38SJeff Roberson  * Schedule a thread to resume execution and record how long it voluntarily
1831ae7a6b38SJeff Roberson  * slept.  We also update the pctcpu, interactivity, and priority.
1832ae7a6b38SJeff Roberson  */
183335e6168fSJeff Roberson void
183435e6168fSJeff Roberson sched_wakeup(struct thread *td)
183535e6168fSJeff Roberson {
183614618990SJeff Roberson 	struct td_sched *ts;
1837ae7a6b38SJeff Roberson 	int slptick;
1838e7d50326SJeff Roberson 
18397b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
184014618990SJeff Roberson 	ts = td->td_sched;
184135e6168fSJeff Roberson 	/*
1842e7d50326SJeff Roberson 	 * If we slept for more than a tick update our interactivity and
1843e7d50326SJeff Roberson 	 * priority.
184435e6168fSJeff Roberson 	 */
1845ae7a6b38SJeff Roberson 	slptick = ts->ts_slptick;
1846ae7a6b38SJeff Roberson 	ts->ts_slptick = 0;
1847ae7a6b38SJeff Roberson 	if (slptick && slptick != ticks) {
18489a93305aSJeff Roberson 		u_int hzticks;
1849f1e8dc4aSJeff Roberson 
1850ae7a6b38SJeff Roberson 		hzticks = (ticks - slptick) << SCHED_TICK_SHIFT;
1851ae7a6b38SJeff Roberson 		ts->ts_slptime += hzticks;
18528460a577SJohn Birrell 		sched_interact_update(td);
185314618990SJeff Roberson 		sched_pctcpu_update(ts);
18548460a577SJohn Birrell 		sched_priority(td);
1855f1e8dc4aSJeff Roberson 	}
185614618990SJeff Roberson 	/* Reset the slice value after we sleep. */
185714618990SJeff Roberson 	ts->ts_slice = sched_slice;
18587a5e5e2aSJeff Roberson 	sched_add(td, SRQ_BORING);
185935e6168fSJeff Roberson }
186035e6168fSJeff Roberson 
186135e6168fSJeff Roberson /*
186235e6168fSJeff Roberson  * Penalize the parent for creating a new child and initialize the child's
186335e6168fSJeff Roberson  * priority.
186435e6168fSJeff Roberson  */
186535e6168fSJeff Roberson void
18668460a577SJohn Birrell sched_fork(struct thread *td, struct thread *child)
186715dc847eSJeff Roberson {
18687b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1869ad1e7d28SJulian Elischer 	sched_fork_thread(td, child);
1870e7d50326SJeff Roberson 	/*
1871e7d50326SJeff Roberson 	 * Penalize the parent and child for forking.
1872e7d50326SJeff Roberson 	 */
1873e7d50326SJeff Roberson 	sched_interact_fork(child);
1874e7d50326SJeff Roberson 	sched_priority(child);
1875ae7a6b38SJeff Roberson 	td->td_sched->ts_runtime += tickincr;
1876e7d50326SJeff Roberson 	sched_interact_update(td);
1877e7d50326SJeff Roberson 	sched_priority(td);
1878ad1e7d28SJulian Elischer }
1879ad1e7d28SJulian Elischer 
1880ae7a6b38SJeff Roberson /*
1881ae7a6b38SJeff Roberson  * Fork a new thread, may be within the same process.
1882ae7a6b38SJeff Roberson  */
1883ad1e7d28SJulian Elischer void
1884ad1e7d28SJulian Elischer sched_fork_thread(struct thread *td, struct thread *child)
1885ad1e7d28SJulian Elischer {
1886ad1e7d28SJulian Elischer 	struct td_sched *ts;
1887ad1e7d28SJulian Elischer 	struct td_sched *ts2;
18888460a577SJohn Birrell 
1889e7d50326SJeff Roberson 	/*
1890e7d50326SJeff Roberson 	 * Initialize child.
1891e7d50326SJeff Roberson 	 */
18927b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1893ed062c8dSJulian Elischer 	sched_newthread(child);
1894ae7a6b38SJeff Roberson 	child->td_lock = TDQ_LOCKPTR(TDQ_SELF());
1895ad1e7d28SJulian Elischer 	ts = td->td_sched;
1896ad1e7d28SJulian Elischer 	ts2 = child->td_sched;
1897ad1e7d28SJulian Elischer 	ts2->ts_cpu = ts->ts_cpu;
1898ad1e7d28SJulian Elischer 	ts2->ts_runq = NULL;
1899e7d50326SJeff Roberson 	/*
1900e7d50326SJeff Roberson 	 * Grab our parents cpu estimation information and priority.
1901e7d50326SJeff Roberson 	 */
1902ad1e7d28SJulian Elischer 	ts2->ts_ticks = ts->ts_ticks;
1903ad1e7d28SJulian Elischer 	ts2->ts_ltick = ts->ts_ltick;
1904ad1e7d28SJulian Elischer 	ts2->ts_ftick = ts->ts_ftick;
1905e7d50326SJeff Roberson 	child->td_user_pri = td->td_user_pri;
1906e7d50326SJeff Roberson 	child->td_base_user_pri = td->td_base_user_pri;
1907e7d50326SJeff Roberson 	/*
1908e7d50326SJeff Roberson 	 * And update interactivity score.
1909e7d50326SJeff Roberson 	 */
1910ae7a6b38SJeff Roberson 	ts2->ts_slptime = ts->ts_slptime;
1911ae7a6b38SJeff Roberson 	ts2->ts_runtime = ts->ts_runtime;
1912e7d50326SJeff Roberson 	ts2->ts_slice = 1;	/* Attempt to quickly learn interactivity. */
191315dc847eSJeff Roberson }
191415dc847eSJeff Roberson 
1915ae7a6b38SJeff Roberson /*
1916ae7a6b38SJeff Roberson  * Adjust the priority class of a thread.
1917ae7a6b38SJeff Roberson  */
191815dc847eSJeff Roberson void
19198460a577SJohn Birrell sched_class(struct thread *td, int class)
192015dc847eSJeff Roberson {
192115dc847eSJeff Roberson 
19227b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
19238460a577SJohn Birrell 	if (td->td_pri_class == class)
192415dc847eSJeff Roberson 		return;
192515dc847eSJeff Roberson 
1926ef1134c9SJeff Roberson #ifdef SMP
1927155b9987SJeff Roberson 	/*
1928155b9987SJeff Roberson 	 * On SMP if we're on the RUNQ we must adjust the transferable
1929155b9987SJeff Roberson 	 * count because could be changing to or from an interrupt
1930155b9987SJeff Roberson 	 * class.
1931155b9987SJeff Roberson 	 */
19327a5e5e2aSJeff Roberson 	if (TD_ON_RUNQ(td)) {
19331e516cf5SJeff Roberson 		struct tdq *tdq;
19341e516cf5SJeff Roberson 
19351e516cf5SJeff Roberson 		tdq = TDQ_CPU(td->td_sched->ts_cpu);
19361e516cf5SJeff Roberson 		if (THREAD_CAN_MIGRATE(td)) {
1937d2ad694cSJeff Roberson 			tdq->tdq_transferable--;
1938d2ad694cSJeff Roberson 			tdq->tdq_group->tdg_transferable--;
193980f86c9fSJeff Roberson 		}
19401e516cf5SJeff Roberson 		td->td_pri_class = class;
19411e516cf5SJeff Roberson 		if (THREAD_CAN_MIGRATE(td)) {
1942d2ad694cSJeff Roberson 			tdq->tdq_transferable++;
1943d2ad694cSJeff Roberson 			tdq->tdq_group->tdg_transferable++;
194480f86c9fSJeff Roberson 		}
1945155b9987SJeff Roberson 	}
1946ef1134c9SJeff Roberson #endif
19478460a577SJohn Birrell 	td->td_pri_class = class;
194835e6168fSJeff Roberson }
194935e6168fSJeff Roberson 
195035e6168fSJeff Roberson /*
195135e6168fSJeff Roberson  * Return some of the child's priority and interactivity to the parent.
195235e6168fSJeff Roberson  */
195335e6168fSJeff Roberson void
1954fc6c30f6SJulian Elischer sched_exit(struct proc *p, struct thread *child)
195535e6168fSJeff Roberson {
1956e7d50326SJeff Roberson 	struct thread *td;
1957141ad61cSJeff Roberson 
19588460a577SJohn Birrell 	CTR3(KTR_SCHED, "sched_exit: %p(%s) prio %d",
1959fc6c30f6SJulian Elischer 	    child, child->td_proc->p_comm, child->td_priority);
19608460a577SJohn Birrell 
19617b20fb19SJeff Roberson 	PROC_SLOCK_ASSERT(p, MA_OWNED);
1962e7d50326SJeff Roberson 	td = FIRST_THREAD_IN_PROC(p);
1963e7d50326SJeff Roberson 	sched_exit_thread(td, child);
1964ad1e7d28SJulian Elischer }
1965ad1e7d28SJulian Elischer 
1966ae7a6b38SJeff Roberson /*
1967ae7a6b38SJeff Roberson  * Penalize another thread for the time spent on this one.  This helps to
1968ae7a6b38SJeff Roberson  * worsen the priority and interactivity of processes which schedule batch
1969ae7a6b38SJeff Roberson  * jobs such as make.  This has little effect on the make process itself but
1970ae7a6b38SJeff Roberson  * causes new processes spawned by it to receive worse scores immediately.
1971ae7a6b38SJeff Roberson  */
1972ad1e7d28SJulian Elischer void
1973fc6c30f6SJulian Elischer sched_exit_thread(struct thread *td, struct thread *child)
1974ad1e7d28SJulian Elischer {
1975fc6c30f6SJulian Elischer 
1976e7d50326SJeff Roberson 	CTR3(KTR_SCHED, "sched_exit_thread: %p(%s) prio %d",
1977e7d50326SJeff Roberson 	    child, child->td_proc->p_comm, child->td_priority);
1978e7d50326SJeff Roberson 
1979e7d50326SJeff Roberson #ifdef KSE
1980e7d50326SJeff Roberson 	/*
1981e7d50326SJeff Roberson 	 * KSE forks and exits so often that this penalty causes short-lived
1982e7d50326SJeff Roberson 	 * threads to always be non-interactive.  This causes mozilla to
1983e7d50326SJeff Roberson 	 * crawl under load.
1984e7d50326SJeff Roberson 	 */
1985e7d50326SJeff Roberson 	if ((td->td_pflags & TDP_SA) && td->td_proc == child->td_proc)
1986e7d50326SJeff Roberson 		return;
1987e7d50326SJeff Roberson #endif
1988e7d50326SJeff Roberson 	/*
1989e7d50326SJeff Roberson 	 * Give the child's runtime to the parent without returning the
1990e7d50326SJeff Roberson 	 * sleep time as a penalty to the parent.  This causes shells that
1991e7d50326SJeff Roberson 	 * launch expensive things to mark their children as expensive.
1992e7d50326SJeff Roberson 	 */
19937b20fb19SJeff Roberson 	thread_lock(td);
1994ae7a6b38SJeff Roberson 	td->td_sched->ts_runtime += child->td_sched->ts_runtime;
1995fc6c30f6SJulian Elischer 	sched_interact_update(td);
1996e7d50326SJeff Roberson 	sched_priority(td);
19977b20fb19SJeff Roberson 	thread_unlock(td);
1998ad1e7d28SJulian Elischer }
1999ad1e7d28SJulian Elischer 
2000ae7a6b38SJeff Roberson /*
2001ae7a6b38SJeff Roberson  * Fix priorities on return to user-space.  Priorities may be elevated due
2002ae7a6b38SJeff Roberson  * to static priorities in msleep() or similar.
2003ae7a6b38SJeff Roberson  */
2004ad1e7d28SJulian Elischer void
2005ad1e7d28SJulian Elischer sched_userret(struct thread *td)
2006ad1e7d28SJulian Elischer {
2007ad1e7d28SJulian Elischer 	/*
2008ad1e7d28SJulian Elischer 	 * XXX we cheat slightly on the locking here to avoid locking in
2009ad1e7d28SJulian Elischer 	 * the usual case.  Setting td_priority here is essentially an
2010ad1e7d28SJulian Elischer 	 * incomplete workaround for not setting it properly elsewhere.
2011ad1e7d28SJulian Elischer 	 * Now that some interrupt handlers are threads, not setting it
2012ad1e7d28SJulian Elischer 	 * properly elsewhere can clobber it in the window between setting
2013ad1e7d28SJulian Elischer 	 * it here and returning to user mode, so don't waste time setting
2014ad1e7d28SJulian Elischer 	 * it perfectly here.
2015ad1e7d28SJulian Elischer 	 */
2016ad1e7d28SJulian Elischer 	KASSERT((td->td_flags & TDF_BORROWING) == 0,
2017ad1e7d28SJulian Elischer 	    ("thread with borrowed priority returning to userland"));
2018ad1e7d28SJulian Elischer 	if (td->td_priority != td->td_user_pri) {
20197b20fb19SJeff Roberson 		thread_lock(td);
2020ad1e7d28SJulian Elischer 		td->td_priority = td->td_user_pri;
2021ad1e7d28SJulian Elischer 		td->td_base_pri = td->td_user_pri;
20227b20fb19SJeff Roberson 		thread_unlock(td);
2023ad1e7d28SJulian Elischer         }
202435e6168fSJeff Roberson }
202535e6168fSJeff Roberson 
2026ae7a6b38SJeff Roberson /*
2027ae7a6b38SJeff Roberson  * Handle a stathz tick.  This is really only relevant for timeshare
2028ae7a6b38SJeff Roberson  * threads.
2029ae7a6b38SJeff Roberson  */
203035e6168fSJeff Roberson void
20317cf90fb3SJeff Roberson sched_clock(struct thread *td)
203235e6168fSJeff Roberson {
2033ad1e7d28SJulian Elischer 	struct tdq *tdq;
2034ad1e7d28SJulian Elischer 	struct td_sched *ts;
203535e6168fSJeff Roberson 
2036ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
20373f872f85SJeff Roberson 	tdq = TDQ_SELF();
20383f872f85SJeff Roberson 	/*
20393f872f85SJeff Roberson 	 * Advance the insert index once for each tick to ensure that all
20403f872f85SJeff Roberson 	 * threads get a chance to run.
20413f872f85SJeff Roberson 	 */
20423f872f85SJeff Roberson 	if (tdq->tdq_idx == tdq->tdq_ridx) {
20433f872f85SJeff Roberson 		tdq->tdq_idx = (tdq->tdq_idx + 1) % RQ_NQS;
20443f872f85SJeff Roberson 		if (TAILQ_EMPTY(&tdq->tdq_timeshare.rq_queues[tdq->tdq_ridx]))
20453f872f85SJeff Roberson 			tdq->tdq_ridx = tdq->tdq_idx;
20463f872f85SJeff Roberson 	}
20473f872f85SJeff Roberson 	ts = td->td_sched;
20483f741ca1SJeff Roberson 	/*
20498460a577SJohn Birrell 	 * We only do slicing code for TIMESHARE threads.
2050a8949de2SJeff Roberson 	 */
20518460a577SJohn Birrell 	if (td->td_pri_class != PRI_TIMESHARE)
2052a8949de2SJeff Roberson 		return;
2053a8949de2SJeff Roberson 	/*
20543f872f85SJeff Roberson 	 * We used a tick; charge it to the thread so that we can compute our
205515dc847eSJeff Roberson 	 * interactivity.
205615dc847eSJeff Roberson 	 */
2057ae7a6b38SJeff Roberson 	td->td_sched->ts_runtime += tickincr;
20588460a577SJohn Birrell 	sched_interact_update(td);
205935e6168fSJeff Roberson 	/*
206035e6168fSJeff Roberson 	 * We used up one time slice.
206135e6168fSJeff Roberson 	 */
2062ad1e7d28SJulian Elischer 	if (--ts->ts_slice > 0)
206315dc847eSJeff Roberson 		return;
206435e6168fSJeff Roberson 	/*
206515dc847eSJeff Roberson 	 * We're out of time, recompute priorities and requeue.
206635e6168fSJeff Roberson 	 */
20678460a577SJohn Birrell 	sched_priority(td);
20684a338afdSJulian Elischer 	td->td_flags |= TDF_NEEDRESCHED;
206935e6168fSJeff Roberson }
207035e6168fSJeff Roberson 
2071ae7a6b38SJeff Roberson /*
2072ae7a6b38SJeff Roberson  * Called once per hz tick.  Used for cpu utilization information.  This
2073ae7a6b38SJeff Roberson  * is easier than trying to scale based on stathz.
2074ae7a6b38SJeff Roberson  */
2075ae7a6b38SJeff Roberson void
2076ae7a6b38SJeff Roberson sched_tick(void)
2077ae7a6b38SJeff Roberson {
2078ae7a6b38SJeff Roberson 	struct td_sched *ts;
2079ae7a6b38SJeff Roberson 
2080ae7a6b38SJeff Roberson 	ts = curthread->td_sched;
2081ae7a6b38SJeff Roberson 	/* Adjust ticks for pctcpu */
2082ae7a6b38SJeff Roberson 	ts->ts_ticks += 1 << SCHED_TICK_SHIFT;
2083ae7a6b38SJeff Roberson 	ts->ts_ltick = ticks;
2084ae7a6b38SJeff Roberson 	/*
2085ae7a6b38SJeff Roberson 	 * Update if we've exceeded our desired tick threshhold by over one
2086ae7a6b38SJeff Roberson 	 * second.
2087ae7a6b38SJeff Roberson 	 */
2088ae7a6b38SJeff Roberson 	if (ts->ts_ftick + SCHED_TICK_MAX < ts->ts_ltick)
2089ae7a6b38SJeff Roberson 		sched_pctcpu_update(ts);
2090ae7a6b38SJeff Roberson }
2091ae7a6b38SJeff Roberson 
2092ae7a6b38SJeff Roberson /*
2093ae7a6b38SJeff Roberson  * Return whether the current CPU has runnable tasks.  Used for in-kernel
2094ae7a6b38SJeff Roberson  * cooperative idle threads.
2095ae7a6b38SJeff Roberson  */
209635e6168fSJeff Roberson int
209735e6168fSJeff Roberson sched_runnable(void)
209835e6168fSJeff Roberson {
2099ad1e7d28SJulian Elischer 	struct tdq *tdq;
2100b90816f1SJeff Roberson 	int load;
210135e6168fSJeff Roberson 
2102b90816f1SJeff Roberson 	load = 1;
2103b90816f1SJeff Roberson 
2104ad1e7d28SJulian Elischer 	tdq = TDQ_SELF();
21053f741ca1SJeff Roberson 	if ((curthread->td_flags & TDF_IDLETD) != 0) {
2106d2ad694cSJeff Roberson 		if (tdq->tdq_load > 0)
21073f741ca1SJeff Roberson 			goto out;
21083f741ca1SJeff Roberson 	} else
2109d2ad694cSJeff Roberson 		if (tdq->tdq_load - 1 > 0)
2110b90816f1SJeff Roberson 			goto out;
2111b90816f1SJeff Roberson 	load = 0;
2112b90816f1SJeff Roberson out:
2113b90816f1SJeff Roberson 	return (load);
211435e6168fSJeff Roberson }
211535e6168fSJeff Roberson 
2116ae7a6b38SJeff Roberson /*
2117ae7a6b38SJeff Roberson  * Choose the highest priority thread to run.  The thread is removed from
2118ae7a6b38SJeff Roberson  * the run-queue while running however the load remains.  For SMP we set
2119ae7a6b38SJeff Roberson  * the tdq in the global idle bitmask if it idles here.
2120ae7a6b38SJeff Roberson  */
21217a5e5e2aSJeff Roberson struct thread *
2122c9f25d8fSJeff Roberson sched_choose(void)
2123c9f25d8fSJeff Roberson {
212415dc847eSJeff Roberson #ifdef SMP
2125ae7a6b38SJeff Roberson 	struct tdq_group *tdg;
212615dc847eSJeff Roberson #endif
2127ae7a6b38SJeff Roberson 	struct td_sched *ts;
2128ae7a6b38SJeff Roberson 	struct tdq *tdq;
2129ae7a6b38SJeff Roberson 
2130ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2131ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2132ad1e7d28SJulian Elischer 	ts = tdq_choose(tdq);
2133ad1e7d28SJulian Elischer 	if (ts) {
2134ad1e7d28SJulian Elischer 		tdq_runq_rem(tdq, ts);
21357a5e5e2aSJeff Roberson 		return (ts->ts_thread);
213635e6168fSJeff Roberson 	}
2137c9f25d8fSJeff Roberson #ifdef SMP
2138ae7a6b38SJeff Roberson 	/*
2139ae7a6b38SJeff Roberson 	 * We only set the idled bit when all of the cpus in the group are
2140ae7a6b38SJeff Roberson 	 * idle.  Otherwise we could get into a situation where a thread bounces
2141ae7a6b38SJeff Roberson 	 * back and forth between two idle cores on seperate physical CPUs.
2142ae7a6b38SJeff Roberson 	 */
2143ae7a6b38SJeff Roberson 	tdg = tdq->tdq_group;
2144ae7a6b38SJeff Roberson 	tdg->tdg_idlemask |= PCPU_GET(cpumask);
2145ae7a6b38SJeff Roberson 	if (tdg->tdg_idlemask == tdg->tdg_cpumask)
2146ae7a6b38SJeff Roberson 		atomic_set_int(&tdq_idle, tdg->tdg_mask);
2147ae7a6b38SJeff Roberson 	tdq->tdq_lowpri = PRI_MAX_IDLE;
2148c9f25d8fSJeff Roberson #endif
21497a5e5e2aSJeff Roberson 	return (PCPU_GET(idlethread));
21507a5e5e2aSJeff Roberson }
21517a5e5e2aSJeff Roberson 
2152ae7a6b38SJeff Roberson /*
2153ae7a6b38SJeff Roberson  * Set owepreempt if necessary.  Preemption never happens directly in ULE,
2154ae7a6b38SJeff Roberson  * we always request it once we exit a critical section.
2155ae7a6b38SJeff Roberson  */
2156ae7a6b38SJeff Roberson static inline void
2157ae7a6b38SJeff Roberson sched_setpreempt(struct thread *td)
21587a5e5e2aSJeff Roberson {
21597a5e5e2aSJeff Roberson 	struct thread *ctd;
21607a5e5e2aSJeff Roberson 	int cpri;
21617a5e5e2aSJeff Roberson 	int pri;
21627a5e5e2aSJeff Roberson 
21637a5e5e2aSJeff Roberson 	ctd = curthread;
21647a5e5e2aSJeff Roberson 	pri = td->td_priority;
21657a5e5e2aSJeff Roberson 	cpri = ctd->td_priority;
2166ae7a6b38SJeff Roberson 	if (td->td_priority < ctd->td_priority)
2167ae7a6b38SJeff Roberson 		curthread->td_flags |= TDF_NEEDRESCHED;
21687a5e5e2aSJeff Roberson 	if (panicstr != NULL || pri >= cpri || cold || TD_IS_INHIBITED(ctd))
2169ae7a6b38SJeff Roberson 		return;
21707a5e5e2aSJeff Roberson 	/*
21717a5e5e2aSJeff Roberson 	 * Always preempt IDLE threads.  Otherwise only if the preempting
21727a5e5e2aSJeff Roberson 	 * thread is an ithread.
21737a5e5e2aSJeff Roberson 	 */
2174ae7a6b38SJeff Roberson 	if (pri > preempt_thresh && cpri < PRI_MIN_IDLE)
2175ae7a6b38SJeff Roberson 		return;
21767a5e5e2aSJeff Roberson 	ctd->td_owepreempt = 1;
2177ae7a6b38SJeff Roberson 	return;
217835e6168fSJeff Roberson }
217935e6168fSJeff Roberson 
2180ae7a6b38SJeff Roberson /*
2181ae7a6b38SJeff Roberson  * Add a thread to a thread queue.  Initializes priority, slice, runq, and
2182ae7a6b38SJeff Roberson  * add it to the appropriate queue.  This is the internal function called
2183ae7a6b38SJeff Roberson  * when the tdq is predetermined.
2184ae7a6b38SJeff Roberson  */
218535e6168fSJeff Roberson void
2186ae7a6b38SJeff Roberson tdq_add(struct tdq *tdq, struct thread *td, int flags)
218735e6168fSJeff Roberson {
2188ad1e7d28SJulian Elischer 	struct td_sched *ts;
218922bf7d9aSJeff Roberson 	int class;
21907b8bfa0dSJeff Roberson #ifdef SMP
21917b8bfa0dSJeff Roberson 	int cpumask;
21927b8bfa0dSJeff Roberson #endif
2193c9f25d8fSJeff Roberson 
2194ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
21957a5e5e2aSJeff Roberson 	KASSERT((td->td_inhibitors == 0),
21967a5e5e2aSJeff Roberson 	    ("sched_add: trying to run inhibited thread"));
21977a5e5e2aSJeff Roberson 	KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
21987a5e5e2aSJeff Roberson 	    ("sched_add: bad thread state"));
21998460a577SJohn Birrell 	KASSERT(td->td_proc->p_sflag & PS_INMEM,
22005d7ef00cSJeff Roberson 	    ("sched_add: process swapped out"));
2201ae7a6b38SJeff Roberson 
2202ae7a6b38SJeff Roberson 	ts = td->td_sched;
22037a5e5e2aSJeff Roberson 	class = PRI_BASE(td->td_pri_class);
2204ae7a6b38SJeff Roberson         TD_SET_RUNQ(td);
22057a5e5e2aSJeff Roberson 	if (ts->ts_slice == 0)
22067a5e5e2aSJeff Roberson 		ts->ts_slice = sched_slice;
22072454aaf5SJeff Roberson 	/*
2208ae7a6b38SJeff Roberson 	 * Pick the run queue based on priority.
22092454aaf5SJeff Roberson 	 */
2210ae7a6b38SJeff Roberson 	if (td->td_priority <= PRI_MAX_REALTIME)
2211ae7a6b38SJeff Roberson 		ts->ts_runq = &tdq->tdq_realtime;
2212ae7a6b38SJeff Roberson 	else if (td->td_priority <= PRI_MAX_TIMESHARE)
2213ae7a6b38SJeff Roberson 		ts->ts_runq = &tdq->tdq_timeshare;
22147b8bfa0dSJeff Roberson 	else
2215ae7a6b38SJeff Roberson 		ts->ts_runq = &tdq->tdq_idle;
2216ae7a6b38SJeff Roberson #ifdef SMP
22177b8bfa0dSJeff Roberson 	cpumask = 1 << ts->ts_cpu;
221822bf7d9aSJeff Roberson 	/*
2219670c524fSJeff Roberson 	 * If we had been idle, clear our bit in the group and potentially
22207b8bfa0dSJeff Roberson 	 * the global bitmap.
222122bf7d9aSJeff Roberson 	 */
2222e7d50326SJeff Roberson 	if ((class != PRI_IDLE && class != PRI_ITHD) &&
22237b8bfa0dSJeff Roberson 	    (tdq->tdq_group->tdg_idlemask & cpumask) != 0) {
222480f86c9fSJeff Roberson 		/*
222580f86c9fSJeff Roberson 		 * Check to see if our group is unidling, and if so, remove it
222680f86c9fSJeff Roberson 		 * from the global idle mask.
222780f86c9fSJeff Roberson 		 */
2228d2ad694cSJeff Roberson 		if (tdq->tdq_group->tdg_idlemask ==
2229d2ad694cSJeff Roberson 		    tdq->tdq_group->tdg_cpumask)
2230d2ad694cSJeff Roberson 			atomic_clear_int(&tdq_idle, tdq->tdq_group->tdg_mask);
223180f86c9fSJeff Roberson 		/*
223280f86c9fSJeff Roberson 		 * Now remove ourselves from the group specific idle mask.
223380f86c9fSJeff Roberson 		 */
22347b8bfa0dSJeff Roberson 		tdq->tdq_group->tdg_idlemask &= ~cpumask;
22357b8bfa0dSJeff Roberson 	}
2236ae7a6b38SJeff Roberson 	if (td->td_priority < tdq->tdq_lowpri)
2237ae7a6b38SJeff Roberson 		tdq->tdq_lowpri = td->td_priority;
223822bf7d9aSJeff Roberson #endif
2239ad1e7d28SJulian Elischer 	tdq_runq_add(tdq, ts, flags);
2240ad1e7d28SJulian Elischer 	tdq_load_add(tdq, ts);
2241ae7a6b38SJeff Roberson }
2242ae7a6b38SJeff Roberson 
2243ae7a6b38SJeff Roberson /*
2244ae7a6b38SJeff Roberson  * Select the target thread queue and add a thread to it.  Request
2245ae7a6b38SJeff Roberson  * preemption or IPI a remote processor if required.
2246ae7a6b38SJeff Roberson  */
2247ae7a6b38SJeff Roberson void
2248ae7a6b38SJeff Roberson sched_add(struct thread *td, int flags)
2249ae7a6b38SJeff Roberson {
2250ae7a6b38SJeff Roberson 	struct td_sched *ts;
2251ae7a6b38SJeff Roberson 	struct tdq *tdq;
22527b8bfa0dSJeff Roberson #ifdef SMP
2253ae7a6b38SJeff Roberson 	int cpuid;
2254ae7a6b38SJeff Roberson 	int cpu;
2255ae7a6b38SJeff Roberson #endif
2256ae7a6b38SJeff Roberson 	CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)",
2257ae7a6b38SJeff Roberson 	    td, td->td_proc->p_comm, td->td_priority, curthread,
2258ae7a6b38SJeff Roberson 	    curthread->td_proc->p_comm);
2259ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2260ae7a6b38SJeff Roberson 	ts = td->td_sched;
2261ae7a6b38SJeff Roberson 	/*
2262ae7a6b38SJeff Roberson 	 * Recalculate the priority before we select the target cpu or
2263ae7a6b38SJeff Roberson 	 * run-queue.
2264ae7a6b38SJeff Roberson 	 */
2265ae7a6b38SJeff Roberson 	if (PRI_BASE(td->td_pri_class) == PRI_TIMESHARE)
2266ae7a6b38SJeff Roberson 		sched_priority(td);
2267ae7a6b38SJeff Roberson #ifdef SMP
2268ae7a6b38SJeff Roberson 	cpuid = PCPU_GET(cpuid);
2269ae7a6b38SJeff Roberson 	/*
2270ae7a6b38SJeff Roberson 	 * Pick the destination cpu and if it isn't ours transfer to the
2271ae7a6b38SJeff Roberson 	 * target cpu.
2272ae7a6b38SJeff Roberson 	 */
2273ae7a6b38SJeff Roberson 	if (td->td_priority <= PRI_MAX_ITHD && THREAD_CAN_MIGRATE(td))
2274ae7a6b38SJeff Roberson 		cpu = cpuid;
2275ae7a6b38SJeff Roberson 	else if (!THREAD_CAN_MIGRATE(td))
2276ae7a6b38SJeff Roberson 		cpu = ts->ts_cpu;
2277ae7a6b38SJeff Roberson 	else
2278ae7a6b38SJeff Roberson 		cpu = sched_pickcpu(ts, flags);
2279ae7a6b38SJeff Roberson 	tdq = sched_setcpu(ts, cpu, flags);
2280ae7a6b38SJeff Roberson 	tdq_add(tdq, td, flags);
2281ae7a6b38SJeff Roberson 	if (cpu != cpuid) {
22827b8bfa0dSJeff Roberson 		tdq_notify(ts);
22837b8bfa0dSJeff Roberson 		return;
22847b8bfa0dSJeff Roberson 	}
2285ae7a6b38SJeff Roberson #else
2286ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2287ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
2288ae7a6b38SJeff Roberson 	/*
2289ae7a6b38SJeff Roberson 	 * Now that the thread is moving to the run-queue, set the lock
2290ae7a6b38SJeff Roberson 	 * to the scheduler's lock.
2291ae7a6b38SJeff Roberson 	 */
2292ae7a6b38SJeff Roberson 	thread_lock_set(td, TDQ_LOCKPTR(tdq));
2293ae7a6b38SJeff Roberson 	tdq_add(tdq, td, flags);
22947b8bfa0dSJeff Roberson #endif
2295ae7a6b38SJeff Roberson 	if (!(flags & SRQ_YIELDING))
2296ae7a6b38SJeff Roberson 		sched_setpreempt(td);
229735e6168fSJeff Roberson }
229835e6168fSJeff Roberson 
2299ae7a6b38SJeff Roberson /*
2300ae7a6b38SJeff Roberson  * Remove a thread from a run-queue without running it.  This is used
2301ae7a6b38SJeff Roberson  * when we're stealing a thread from a remote queue.  Otherwise all threads
2302ae7a6b38SJeff Roberson  * exit by calling sched_exit_thread() and sched_throw() themselves.
2303ae7a6b38SJeff Roberson  */
230435e6168fSJeff Roberson void
23057cf90fb3SJeff Roberson sched_rem(struct thread *td)
230635e6168fSJeff Roberson {
2307ad1e7d28SJulian Elischer 	struct tdq *tdq;
2308ad1e7d28SJulian Elischer 	struct td_sched *ts;
23097cf90fb3SJeff Roberson 
231081d47d3fSJeff Roberson 	CTR5(KTR_SCHED, "sched_rem: %p(%s) prio %d by %p(%s)",
231181d47d3fSJeff Roberson 	    td, td->td_proc->p_comm, td->td_priority, curthread,
231281d47d3fSJeff Roberson 	    curthread->td_proc->p_comm);
2313ad1e7d28SJulian Elischer 	ts = td->td_sched;
2314ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(ts->ts_cpu);
2315ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2316ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
23177a5e5e2aSJeff Roberson 	KASSERT(TD_ON_RUNQ(td),
2318ad1e7d28SJulian Elischer 	    ("sched_rem: thread not on run queue"));
2319ad1e7d28SJulian Elischer 	tdq_runq_rem(tdq, ts);
2320ad1e7d28SJulian Elischer 	tdq_load_rem(tdq, ts);
23217a5e5e2aSJeff Roberson 	TD_SET_CAN_RUN(td);
232235e6168fSJeff Roberson }
232335e6168fSJeff Roberson 
2324ae7a6b38SJeff Roberson /*
2325ae7a6b38SJeff Roberson  * Fetch cpu utilization information.  Updates on demand.
2326ae7a6b38SJeff Roberson  */
232735e6168fSJeff Roberson fixpt_t
23287cf90fb3SJeff Roberson sched_pctcpu(struct thread *td)
232935e6168fSJeff Roberson {
233035e6168fSJeff Roberson 	fixpt_t pctcpu;
2331ad1e7d28SJulian Elischer 	struct td_sched *ts;
233235e6168fSJeff Roberson 
233335e6168fSJeff Roberson 	pctcpu = 0;
2334ad1e7d28SJulian Elischer 	ts = td->td_sched;
2335ad1e7d28SJulian Elischer 	if (ts == NULL)
2336484288deSJeff Roberson 		return (0);
233735e6168fSJeff Roberson 
23387b20fb19SJeff Roberson 	thread_lock(td);
2339ad1e7d28SJulian Elischer 	if (ts->ts_ticks) {
234035e6168fSJeff Roberson 		int rtick;
234135e6168fSJeff Roberson 
2342ad1e7d28SJulian Elischer 		sched_pctcpu_update(ts);
234335e6168fSJeff Roberson 		/* How many rtick per second ? */
2344e7d50326SJeff Roberson 		rtick = min(SCHED_TICK_HZ(ts) / SCHED_TICK_SECS, hz);
2345e7d50326SJeff Roberson 		pctcpu = (FSCALE * ((FSCALE * rtick)/hz)) >> FSHIFT;
234635e6168fSJeff Roberson 	}
2347ad1e7d28SJulian Elischer 	td->td_proc->p_swtime = ts->ts_ltick - ts->ts_ftick;
23487b20fb19SJeff Roberson 	thread_unlock(td);
234935e6168fSJeff Roberson 
235035e6168fSJeff Roberson 	return (pctcpu);
235135e6168fSJeff Roberson }
235235e6168fSJeff Roberson 
2353ae7a6b38SJeff Roberson /*
2354ae7a6b38SJeff Roberson  * Bind a thread to a target cpu.
2355ae7a6b38SJeff Roberson  */
23569bacd788SJeff Roberson void
23579bacd788SJeff Roberson sched_bind(struct thread *td, int cpu)
23589bacd788SJeff Roberson {
2359ad1e7d28SJulian Elischer 	struct td_sched *ts;
23609bacd788SJeff Roberson 
23617b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2362ad1e7d28SJulian Elischer 	ts = td->td_sched;
23636b2f763fSJeff Roberson 	if (ts->ts_flags & TSF_BOUND)
2364c95d2db2SJeff Roberson 		sched_unbind(td);
2365ad1e7d28SJulian Elischer 	ts->ts_flags |= TSF_BOUND;
236680f86c9fSJeff Roberson #ifdef SMP
23676b2f763fSJeff Roberson 	sched_pin();
236880f86c9fSJeff Roberson 	if (PCPU_GET(cpuid) == cpu)
23699bacd788SJeff Roberson 		return;
23706b2f763fSJeff Roberson 	ts->ts_cpu = cpu;
23719bacd788SJeff Roberson 	/* When we return from mi_switch we'll be on the correct cpu. */
2372279f949eSPoul-Henning Kamp 	mi_switch(SW_VOL, NULL);
23739bacd788SJeff Roberson #endif
23749bacd788SJeff Roberson }
23759bacd788SJeff Roberson 
2376ae7a6b38SJeff Roberson /*
2377ae7a6b38SJeff Roberson  * Release a bound thread.
2378ae7a6b38SJeff Roberson  */
23799bacd788SJeff Roberson void
23809bacd788SJeff Roberson sched_unbind(struct thread *td)
23819bacd788SJeff Roberson {
2382e7d50326SJeff Roberson 	struct td_sched *ts;
2383e7d50326SJeff Roberson 
23847b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2385e7d50326SJeff Roberson 	ts = td->td_sched;
23866b2f763fSJeff Roberson 	if ((ts->ts_flags & TSF_BOUND) == 0)
23876b2f763fSJeff Roberson 		return;
2388e7d50326SJeff Roberson 	ts->ts_flags &= ~TSF_BOUND;
2389e7d50326SJeff Roberson #ifdef SMP
2390e7d50326SJeff Roberson 	sched_unpin();
2391e7d50326SJeff Roberson #endif
23929bacd788SJeff Roberson }
23939bacd788SJeff Roberson 
239435e6168fSJeff Roberson int
2395ebccf1e3SJoseph Koshy sched_is_bound(struct thread *td)
2396ebccf1e3SJoseph Koshy {
23977b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2398ad1e7d28SJulian Elischer 	return (td->td_sched->ts_flags & TSF_BOUND);
2399ebccf1e3SJoseph Koshy }
2400ebccf1e3SJoseph Koshy 
2401ae7a6b38SJeff Roberson /*
2402ae7a6b38SJeff Roberson  * Basic yield call.
2403ae7a6b38SJeff Roberson  */
240436ec198bSDavid Xu void
240536ec198bSDavid Xu sched_relinquish(struct thread *td)
240636ec198bSDavid Xu {
24077b20fb19SJeff Roberson 	thread_lock(td);
24088460a577SJohn Birrell 	if (td->td_pri_class == PRI_TIMESHARE)
240936ec198bSDavid Xu 		sched_prio(td, PRI_MAX_TIMESHARE);
24107b20fb19SJeff Roberson 	SCHED_STAT_INC(switch_relinquish);
241136ec198bSDavid Xu 	mi_switch(SW_VOL, NULL);
24127b20fb19SJeff Roberson 	thread_unlock(td);
241336ec198bSDavid Xu }
241436ec198bSDavid Xu 
2415ae7a6b38SJeff Roberson /*
2416ae7a6b38SJeff Roberson  * Return the total system load.
2417ae7a6b38SJeff Roberson  */
2418ebccf1e3SJoseph Koshy int
241933916c36SJeff Roberson sched_load(void)
242033916c36SJeff Roberson {
242133916c36SJeff Roberson #ifdef SMP
242233916c36SJeff Roberson 	int total;
242333916c36SJeff Roberson 	int i;
242433916c36SJeff Roberson 
242533916c36SJeff Roberson 	total = 0;
2426d2ad694cSJeff Roberson 	for (i = 0; i <= tdg_maxid; i++)
2427d2ad694cSJeff Roberson 		total += TDQ_GROUP(i)->tdg_load;
242833916c36SJeff Roberson 	return (total);
242933916c36SJeff Roberson #else
2430d2ad694cSJeff Roberson 	return (TDQ_SELF()->tdq_sysload);
243133916c36SJeff Roberson #endif
243233916c36SJeff Roberson }
243333916c36SJeff Roberson 
243433916c36SJeff Roberson int
243535e6168fSJeff Roberson sched_sizeof_proc(void)
243635e6168fSJeff Roberson {
243735e6168fSJeff Roberson 	return (sizeof(struct proc));
243835e6168fSJeff Roberson }
243935e6168fSJeff Roberson 
244035e6168fSJeff Roberson int
244135e6168fSJeff Roberson sched_sizeof_thread(void)
244235e6168fSJeff Roberson {
244335e6168fSJeff Roberson 	return (sizeof(struct thread) + sizeof(struct td_sched));
244435e6168fSJeff Roberson }
2445b41f1452SDavid Xu 
24467a5e5e2aSJeff Roberson /*
24477a5e5e2aSJeff Roberson  * The actual idle process.
24487a5e5e2aSJeff Roberson  */
24497a5e5e2aSJeff Roberson void
24507a5e5e2aSJeff Roberson sched_idletd(void *dummy)
24517a5e5e2aSJeff Roberson {
24527a5e5e2aSJeff Roberson 	struct thread *td;
2453ae7a6b38SJeff Roberson 	struct tdq *tdq;
24547a5e5e2aSJeff Roberson 
24557a5e5e2aSJeff Roberson 	td = curthread;
2456ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
24577a5e5e2aSJeff Roberson 	mtx_assert(&Giant, MA_NOTOWNED);
2458ae7a6b38SJeff Roberson 	/* ULE relies on preemption for idle interruption. */
2459ae7a6b38SJeff Roberson 	for (;;) {
2460ae7a6b38SJeff Roberson #ifdef SMP
2461ae7a6b38SJeff Roberson 		if (tdq_idled(tdq))
24627a5e5e2aSJeff Roberson 			cpu_idle();
2463ae7a6b38SJeff Roberson #else
2464ae7a6b38SJeff Roberson 		cpu_idle();
2465ae7a6b38SJeff Roberson #endif
2466ae7a6b38SJeff Roberson 	}
2467b41f1452SDavid Xu }
2468e7d50326SJeff Roberson 
24697b20fb19SJeff Roberson /*
24707b20fb19SJeff Roberson  * A CPU is entering for the first time or a thread is exiting.
24717b20fb19SJeff Roberson  */
24727b20fb19SJeff Roberson void
24737b20fb19SJeff Roberson sched_throw(struct thread *td)
24747b20fb19SJeff Roberson {
2475ae7a6b38SJeff Roberson 	struct tdq *tdq;
2476ae7a6b38SJeff Roberson 
2477ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
24787b20fb19SJeff Roberson 	if (td == NULL) {
2479ae7a6b38SJeff Roberson 		/* Correct spinlock nesting and acquire the correct lock. */
2480ae7a6b38SJeff Roberson 		TDQ_LOCK(tdq);
24817b20fb19SJeff Roberson 		spinlock_exit();
24827b20fb19SJeff Roberson 	} else {
2483ae7a6b38SJeff Roberson 		MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
2484ae7a6b38SJeff Roberson 		tdq_load_rem(tdq, td->td_sched);
24857b20fb19SJeff Roberson 	}
24867b20fb19SJeff Roberson 	KASSERT(curthread->td_md.md_spinlock_count == 1, ("invalid count"));
24877b20fb19SJeff Roberson 	PCPU_SET(switchtime, cpu_ticks());
24887b20fb19SJeff Roberson 	PCPU_SET(switchticks, ticks);
24897b20fb19SJeff Roberson 	cpu_throw(td, choosethread());	/* doesn't return */
24907b20fb19SJeff Roberson }
24917b20fb19SJeff Roberson 
2492ae7a6b38SJeff Roberson /*
2493ae7a6b38SJeff Roberson  * This is called from fork_exit().  Just acquire the correct locks and
2494ae7a6b38SJeff Roberson  * let fork do the rest of the work.
2495ae7a6b38SJeff Roberson  */
24967b20fb19SJeff Roberson void
2497fe54587fSJeff Roberson sched_fork_exit(struct thread *td)
24987b20fb19SJeff Roberson {
2499ae7a6b38SJeff Roberson 	struct td_sched *ts;
2500ae7a6b38SJeff Roberson 	struct tdq *tdq;
2501ae7a6b38SJeff Roberson 	int cpuid;
25027b20fb19SJeff Roberson 
25037b20fb19SJeff Roberson 	/*
25047b20fb19SJeff Roberson 	 * Finish setting up thread glue so that it begins execution in a
2505ae7a6b38SJeff Roberson 	 * non-nested critical section with the scheduler lock held.
25067b20fb19SJeff Roberson 	 */
2507ae7a6b38SJeff Roberson 	cpuid = PCPU_GET(cpuid);
2508ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpuid);
2509ae7a6b38SJeff Roberson 	ts = td->td_sched;
2510ae7a6b38SJeff Roberson 	if (TD_IS_IDLETHREAD(td))
2511ae7a6b38SJeff Roberson 		td->td_lock = TDQ_LOCKPTR(tdq);
2512ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
2513ae7a6b38SJeff Roberson 	td->td_oncpu = cpuid;
2514ae7a6b38SJeff Roberson 	TDQ_LOCKPTR(tdq)->mtx_lock = (uintptr_t)td;
2515fe54587fSJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED | MA_NOTRECURSED);
25167b20fb19SJeff Roberson }
25177b20fb19SJeff Roberson 
2518ae7a6b38SJeff Roberson static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0,
2519ae7a6b38SJeff Roberson     "Scheduler");
2520ae7a6b38SJeff Roberson SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "ULE", 0,
2521e7d50326SJeff Roberson     "Scheduler name");
2522ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice, CTLFLAG_RW, &sched_slice, 0,
2523ae7a6b38SJeff Roberson     "Slice size for timeshare threads");
2524ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, interact, CTLFLAG_RW, &sched_interact, 0,
2525ae7a6b38SJeff Roberson      "Interactivity score threshold");
2526ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, preempt_thresh, CTLFLAG_RW, &preempt_thresh,
2527ae7a6b38SJeff Roberson      0,"Min priority for preemption, lower priorities have greater precedence");
25287b8bfa0dSJeff Roberson #ifdef SMP
2529ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, pick_pri, CTLFLAG_RW, &pick_pri, 0,
2530ae7a6b38SJeff Roberson     "Pick the target cpu based on priority rather than load.");
2531ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, pick_zero, CTLFLAG_RW, &pick_zero, 0,
2532ae7a6b38SJeff Roberson     "If there are no idle cpus pick cpu0");
2533ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, affinity, CTLFLAG_RW, &affinity, 0,
2534ae7a6b38SJeff Roberson     "Number of hz ticks to keep thread affinity for");
2535ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, tryself, CTLFLAG_RW, &tryself, 0, "");
2536ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, tryselfidle, CTLFLAG_RW,
25377b8bfa0dSJeff Roberson     &tryselfidle, 0, "");
2538ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, balance, CTLFLAG_RW, &rebalance, 0,
2539ae7a6b38SJeff Roberson     "Enables the long-term load balancer");
2540ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, steal_htt, CTLFLAG_RW, &steal_htt, 0,
2541ae7a6b38SJeff Roberson     "Steals work from another hyper-threaded core on idle");
2542ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, steal_idle, CTLFLAG_RW, &steal_idle, 0,
2543ae7a6b38SJeff Roberson     "Attempts to steal work from other cores before idling");
2544ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, topology, CTLFLAG_RD, &topology, 0,
2545ae7a6b38SJeff Roberson     "True when a topology has been specified by the MD code.");
25467b8bfa0dSJeff Roberson #endif
2547e7d50326SJeff Roberson 
2548e7d50326SJeff Roberson /* ps compat */
2549e7d50326SJeff Roberson static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
2550e7d50326SJeff Roberson SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
2551e7d50326SJeff Roberson 
2552e7d50326SJeff Roberson 
2553ed062c8dSJulian Elischer #define KERN_SWITCH_INCLUDE 1
2554ed062c8dSJulian Elischer #include "kern/kern_switch.c"
2555