xref: /freebsd/sys/kern/sched_ule.c (revision 7813302434b62f104b26cc6e62cf32d785ee9b7f)
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:
33a5423ea3SJeff Roberson  *   ULE is the last three letters in schedule.  It owes its 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>
39113dda8aSJeff Roberson __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>
49c149e542SAttilio Rao #include <sys/limits.h>
5035e6168fSJeff Roberson #include <sys/lock.h>
5135e6168fSJeff Roberson #include <sys/mutex.h>
5235e6168fSJeff Roberson #include <sys/proc.h>
53245f3abfSJeff Roberson #include <sys/resource.h>
549bacd788SJeff Roberson #include <sys/resourcevar.h>
5535e6168fSJeff Roberson #include <sys/sched.h>
56b3e9e682SRyan Stone #include <sys/sdt.h>
5735e6168fSJeff Roberson #include <sys/smp.h>
5835e6168fSJeff Roberson #include <sys/sx.h>
5935e6168fSJeff Roberson #include <sys/sysctl.h>
6035e6168fSJeff Roberson #include <sys/sysproto.h>
61f5c157d9SJohn Baldwin #include <sys/turnstile.h>
623db720fdSDavid Xu #include <sys/umtx.h>
6335e6168fSJeff Roberson #include <sys/vmmeter.h>
6462fa74d9SJeff Roberson #include <sys/cpuset.h>
6507095abfSIvan Voras #include <sys/sbuf.h>
6635e6168fSJeff Roberson 
67ebccf1e3SJoseph Koshy #ifdef HWPMC_HOOKS
68ebccf1e3SJoseph Koshy #include <sys/pmckern.h>
69ebccf1e3SJoseph Koshy #endif
70ebccf1e3SJoseph Koshy 
716f5f25e5SJohn Birrell #ifdef KDTRACE_HOOKS
726f5f25e5SJohn Birrell #include <sys/dtrace_bsd.h>
736f5f25e5SJohn Birrell int				dtrace_vtime_active;
746f5f25e5SJohn Birrell dtrace_vtime_switch_func_t	dtrace_vtime_switch_func;
756f5f25e5SJohn Birrell #endif
766f5f25e5SJohn Birrell 
7735e6168fSJeff Roberson #include <machine/cpu.h>
7822bf7d9aSJeff Roberson #include <machine/smp.h>
7935e6168fSJeff Roberson 
80ae7a6b38SJeff Roberson #define	KTR_ULE	0
8114618990SJeff Roberson 
820d2cf837SJeff Roberson #define	TS_NAME_LEN (MAXCOMLEN + sizeof(" td ") + sizeof(__XSTRING(UINT_MAX)))
830d2cf837SJeff Roberson #define	TDQ_NAME_LEN	(sizeof("sched lock ") + sizeof(__XSTRING(MAXCPU)))
846338c579SAttilio Rao #define	TDQ_LOADNAME_LEN	(sizeof("CPU ") + sizeof(__XSTRING(MAXCPU)) - 1 + sizeof(" load"))
858f51ad55SJeff Roberson 
866b2f763fSJeff Roberson /*
87ae7a6b38SJeff Roberson  * Thread scheduler specific section.  All fields are protected
88ae7a6b38SJeff Roberson  * by the thread lock.
89ed062c8dSJulian Elischer  */
90ad1e7d28SJulian Elischer struct td_sched {
91ae7a6b38SJeff Roberson 	struct runq	*ts_runq;	/* Run-queue we're queued on. */
92ae7a6b38SJeff Roberson 	short		ts_flags;	/* TSF_* flags. */
93e77f9fedSAdrian Chadd 	int		ts_cpu;		/* CPU that we have affinity for. */
9473daf66fSJeff Roberson 	int		ts_rltick;	/* Real last tick, for affinity. */
95ae7a6b38SJeff Roberson 	int		ts_slice;	/* Ticks of slice remaining. */
96ae7a6b38SJeff Roberson 	u_int		ts_slptime;	/* Number of ticks we vol. slept */
97ae7a6b38SJeff Roberson 	u_int		ts_runtime;	/* Number of ticks we were running */
98ad1e7d28SJulian Elischer 	int		ts_ltick;	/* Last tick that we were running on */
99ad1e7d28SJulian Elischer 	int		ts_ftick;	/* First tick that we were running on */
100ad1e7d28SJulian Elischer 	int		ts_ticks;	/* Tick count */
1018f51ad55SJeff Roberson #ifdef KTR
1028f51ad55SJeff Roberson 	char		ts_name[TS_NAME_LEN];
1038f51ad55SJeff Roberson #endif
104ed062c8dSJulian Elischer };
105ad1e7d28SJulian Elischer /* flags kept in ts_flags */
1067b8bfa0dSJeff Roberson #define	TSF_BOUND	0x0001		/* Thread can not migrate. */
1077b8bfa0dSJeff Roberson #define	TSF_XFERABLE	0x0002		/* Thread was added as transferable. */
10835e6168fSJeff Roberson 
10962fa74d9SJeff Roberson #define	THREAD_CAN_MIGRATE(td)	((td)->td_pinned == 0)
11062fa74d9SJeff Roberson #define	THREAD_CAN_SCHED(td, cpu)	\
11162fa74d9SJeff Roberson     CPU_ISSET((cpu), &(td)->td_cpuset->cs_mask)
11262fa74d9SJeff Roberson 
11393ccd6bfSKonstantin Belousov _Static_assert(sizeof(struct thread) + sizeof(struct td_sched) <=
11493ccd6bfSKonstantin Belousov     sizeof(struct thread0_storage),
11593ccd6bfSKonstantin Belousov     "increase struct thread0_storage.t0st_sched size");
11693ccd6bfSKonstantin Belousov 
11735e6168fSJeff Roberson /*
11812d56c0fSJohn Baldwin  * Priority ranges used for interactive and non-interactive timeshare
1192dc29adbSJohn Baldwin  * threads.  The timeshare priorities are split up into four ranges.
1202dc29adbSJohn Baldwin  * The first range handles interactive threads.  The last three ranges
1212dc29adbSJohn Baldwin  * (NHALF, x, and NHALF) handle non-interactive threads with the outer
1222dc29adbSJohn Baldwin  * ranges supporting nice values.
12312d56c0fSJohn Baldwin  */
1242dc29adbSJohn Baldwin #define	PRI_TIMESHARE_RANGE	(PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
1252dc29adbSJohn Baldwin #define	PRI_INTERACT_RANGE	((PRI_TIMESHARE_RANGE - SCHED_PRI_NRESV) / 2)
12616705791SAndriy Gapon #define	PRI_BATCH_RANGE		(PRI_TIMESHARE_RANGE - PRI_INTERACT_RANGE)
1272dc29adbSJohn Baldwin 
1282dc29adbSJohn Baldwin #define	PRI_MIN_INTERACT	PRI_MIN_TIMESHARE
1292dc29adbSJohn Baldwin #define	PRI_MAX_INTERACT	(PRI_MIN_TIMESHARE + PRI_INTERACT_RANGE - 1)
1302dc29adbSJohn Baldwin #define	PRI_MIN_BATCH		(PRI_MIN_TIMESHARE + PRI_INTERACT_RANGE)
13112d56c0fSJohn Baldwin #define	PRI_MAX_BATCH		PRI_MAX_TIMESHARE
13212d56c0fSJohn Baldwin 
13312d56c0fSJohn Baldwin /*
134e7d50326SJeff Roberson  * Cpu percentage computation macros and defines.
135e1f89c22SJeff Roberson  *
136e7d50326SJeff Roberson  * SCHED_TICK_SECS:	Number of seconds to average the cpu usage across.
137e7d50326SJeff Roberson  * SCHED_TICK_TARG:	Number of hz ticks to average the cpu usage across.
1388ab80cf0SJeff Roberson  * SCHED_TICK_MAX:	Maximum number of ticks before scaling back.
139e7d50326SJeff Roberson  * SCHED_TICK_SHIFT:	Shift factor to avoid rounding away results.
140e7d50326SJeff Roberson  * SCHED_TICK_HZ:	Compute the number of hz ticks for a given ticks count.
141e7d50326SJeff Roberson  * SCHED_TICK_TOTAL:	Gives the amount of time we've been recording ticks.
14235e6168fSJeff Roberson  */
143e7d50326SJeff Roberson #define	SCHED_TICK_SECS		10
144e7d50326SJeff Roberson #define	SCHED_TICK_TARG		(hz * SCHED_TICK_SECS)
1458ab80cf0SJeff Roberson #define	SCHED_TICK_MAX		(SCHED_TICK_TARG + hz)
146e7d50326SJeff Roberson #define	SCHED_TICK_SHIFT	10
147e7d50326SJeff Roberson #define	SCHED_TICK_HZ(ts)	((ts)->ts_ticks >> SCHED_TICK_SHIFT)
148eddb4efaSJeff Roberson #define	SCHED_TICK_TOTAL(ts)	(max((ts)->ts_ltick - (ts)->ts_ftick, hz))
14935e6168fSJeff Roberson 
15035e6168fSJeff Roberson /*
151e7d50326SJeff Roberson  * These macros determine priorities for non-interactive threads.  They are
152e7d50326SJeff Roberson  * assigned a priority based on their recent cpu utilization as expressed
153e7d50326SJeff Roberson  * by the ratio of ticks to the tick total.  NHALF priorities at the start
154e7d50326SJeff Roberson  * and end of the MIN to MAX timeshare range are only reachable with negative
155e7d50326SJeff Roberson  * or positive nice respectively.
156e7d50326SJeff Roberson  *
157e7d50326SJeff Roberson  * PRI_RANGE:	Priority range for utilization dependent priorities.
158e7d50326SJeff Roberson  * PRI_NRESV:	Number of nice values.
159e7d50326SJeff Roberson  * PRI_TICKS:	Compute a priority in PRI_RANGE from the ticks count and total.
160e7d50326SJeff Roberson  * PRI_NICE:	Determines the part of the priority inherited from nice.
161e7d50326SJeff Roberson  */
162e7d50326SJeff Roberson #define	SCHED_PRI_NRESV		(PRIO_MAX - PRIO_MIN)
163e7d50326SJeff Roberson #define	SCHED_PRI_NHALF		(SCHED_PRI_NRESV / 2)
16412d56c0fSJohn Baldwin #define	SCHED_PRI_MIN		(PRI_MIN_BATCH + SCHED_PRI_NHALF)
16512d56c0fSJohn Baldwin #define	SCHED_PRI_MAX		(PRI_MAX_BATCH - SCHED_PRI_NHALF)
16678920008SJohn Baldwin #define	SCHED_PRI_RANGE		(SCHED_PRI_MAX - SCHED_PRI_MIN + 1)
167e7d50326SJeff Roberson #define	SCHED_PRI_TICKS(ts)						\
168e7d50326SJeff Roberson     (SCHED_TICK_HZ((ts)) /						\
1691e516cf5SJeff Roberson     (roundup(SCHED_TICK_TOTAL((ts)), SCHED_PRI_RANGE) / SCHED_PRI_RANGE))
170e7d50326SJeff Roberson #define	SCHED_PRI_NICE(nice)	(nice)
171e7d50326SJeff Roberson 
172e7d50326SJeff Roberson /*
173e7d50326SJeff Roberson  * These determine the interactivity of a process.  Interactivity differs from
174e7d50326SJeff Roberson  * cpu utilization in that it expresses the voluntary time slept vs time ran
175e7d50326SJeff Roberson  * while cpu utilization includes all time not running.  This more accurately
176e7d50326SJeff Roberson  * models the intent of the thread.
17735e6168fSJeff Roberson  *
178407b0157SJeff Roberson  * SLP_RUN_MAX:	Maximum amount of sleep time + run time we'll accumulate
179407b0157SJeff Roberson  *		before throttling back.
180d322132cSJeff Roberson  * SLP_RUN_FORK:	Maximum slp+run time to inherit at fork time.
181210491d3SJeff Roberson  * INTERACT_MAX:	Maximum interactivity value.  Smaller is better.
1829f518f20SAttilio Rao  * INTERACT_THRESH:	Threshold for placement on the current runq.
18335e6168fSJeff Roberson  */
184e7d50326SJeff Roberson #define	SCHED_SLP_RUN_MAX	((hz * 5) << SCHED_TICK_SHIFT)
185e7d50326SJeff Roberson #define	SCHED_SLP_RUN_FORK	((hz / 2) << SCHED_TICK_SHIFT)
186210491d3SJeff Roberson #define	SCHED_INTERACT_MAX	(100)
187210491d3SJeff Roberson #define	SCHED_INTERACT_HALF	(SCHED_INTERACT_MAX / 2)
1884c9612c6SJeff Roberson #define	SCHED_INTERACT_THRESH	(30)
189e1f89c22SJeff Roberson 
1905e5c3873SJeff Roberson /*
1915e5c3873SJeff Roberson  * These parameters determine the slice behavior for batch work.
1925e5c3873SJeff Roberson  */
1935e5c3873SJeff Roberson #define	SCHED_SLICE_DEFAULT_DIVISOR	10	/* ~94 ms, 12 stathz ticks. */
1945e5c3873SJeff Roberson #define	SCHED_SLICE_MIN_DIVISOR		6	/* DEFAULT/MIN = ~16 ms. */
1955e5c3873SJeff Roberson 
1963d7f4117SAlexander Motin /* Flags kept in td_flags. */
1973d7f4117SAlexander Motin #define	TDF_SLICEEND	TDF_SCHED2	/* Thread time slice is over. */
1983d7f4117SAlexander Motin 
19935e6168fSJeff Roberson /*
200e7d50326SJeff Roberson  * tickincr:		Converts a stathz tick into a hz domain scaled by
201e7d50326SJeff Roberson  *			the shift factor.  Without the shift the error rate
202e7d50326SJeff Roberson  *			due to rounding would be unacceptably high.
203e7d50326SJeff Roberson  * realstathz:		stathz is sometimes 0 and run off of hz.
204e7d50326SJeff Roberson  * sched_slice:		Runtime of each thread before rescheduling.
205ae7a6b38SJeff Roberson  * preempt_thresh:	Priority threshold for preemption and remote IPIs.
20635e6168fSJeff Roberson  */
207e7d50326SJeff Roberson static int sched_interact = SCHED_INTERACT_THRESH;
208db702c59SEitan Adler static int tickincr = 8 << SCHED_TICK_SHIFT;
2095e5c3873SJeff Roberson static int realstathz = 127;	/* reset during boot. */
2105e5c3873SJeff Roberson static int sched_slice = 10;	/* reset during boot. */
2115e5c3873SJeff Roberson static int sched_slice_min = 1;	/* reset during boot. */
21202e2d6b4SJeff Roberson #ifdef PREEMPTION
21302e2d6b4SJeff Roberson #ifdef FULL_PREEMPTION
21402e2d6b4SJeff Roberson static int preempt_thresh = PRI_MAX_IDLE;
21502e2d6b4SJeff Roberson #else
216ae7a6b38SJeff Roberson static int preempt_thresh = PRI_MIN_KERN;
21702e2d6b4SJeff Roberson #endif
21802e2d6b4SJeff Roberson #else
21902e2d6b4SJeff Roberson static int preempt_thresh = 0;
22002e2d6b4SJeff Roberson #endif
22112d56c0fSJohn Baldwin static int static_boost = PRI_MIN_BATCH;
2221690c6c1SJeff Roberson static int sched_idlespins = 10000;
223b3f40a41SAlexander Motin static int sched_idlespinthresh = -1;
224ae7a6b38SJeff Roberson 
22535e6168fSJeff Roberson /*
226ae7a6b38SJeff Roberson  * tdq - per processor runqs and statistics.  All fields are protected by the
227ae7a6b38SJeff Roberson  * tdq_lock.  The load and lowpri may be accessed without to avoid excess
228ae7a6b38SJeff Roberson  * locking in sched_pickcpu();
22935e6168fSJeff Roberson  */
230ad1e7d28SJulian Elischer struct tdq {
23139f819e2SJim Harris 	/*
23239f819e2SJim Harris 	 * Ordered to improve efficiency of cpu_search() and switch().
23339f819e2SJim Harris 	 * tdq_lock is padded to avoid false sharing with tdq_load and
23439f819e2SJim Harris 	 * tdq_cpu_idle.
23539f819e2SJim Harris 	 */
2364ceaf45dSAttilio Rao 	struct mtx_padalign tdq_lock;		/* run queue lock. */
23773daf66fSJeff Roberson 	struct cpu_group *tdq_cg;		/* Pointer to cpu topology. */
2381690c6c1SJeff Roberson 	volatile int	tdq_load;		/* Aggregate load. */
2399f9ad565SAlexander Motin 	volatile int	tdq_cpu_idle;		/* cpu_idle() is active. */
24073daf66fSJeff Roberson 	int		tdq_sysload;		/* For loadavg, !ITHD load. */
24173daf66fSJeff Roberson 	int		tdq_transferable;	/* Transferable thread count. */
2421690c6c1SJeff Roberson 	short		tdq_switchcnt;		/* Switches this tick. */
2431690c6c1SJeff Roberson 	short		tdq_oldswitchcnt;	/* Switches last tick. */
24473daf66fSJeff Roberson 	u_char		tdq_lowpri;		/* Lowest priority thread. */
24573daf66fSJeff Roberson 	u_char		tdq_ipipending;		/* IPI pending. */
24673daf66fSJeff Roberson 	u_char		tdq_idx;		/* Current insert index. */
24773daf66fSJeff Roberson 	u_char		tdq_ridx;		/* Current removal index. */
248e7d50326SJeff Roberson 	struct runq	tdq_realtime;		/* real-time run queue. */
249ae7a6b38SJeff Roberson 	struct runq	tdq_timeshare;		/* timeshare run queue. */
250ae7a6b38SJeff Roberson 	struct runq	tdq_idle;		/* Queue of IDLE threads. */
2518f51ad55SJeff Roberson 	char		tdq_name[TDQ_NAME_LEN];
2528f51ad55SJeff Roberson #ifdef KTR
2538f51ad55SJeff Roberson 	char		tdq_loadname[TDQ_LOADNAME_LEN];
2548f51ad55SJeff Roberson #endif
255ae7a6b38SJeff Roberson } __aligned(64);
25635e6168fSJeff Roberson 
2571690c6c1SJeff Roberson /* Idle thread states and config. */
2581690c6c1SJeff Roberson #define	TDQ_RUNNING	1
2591690c6c1SJeff Roberson #define	TDQ_IDLE	2
2607b8bfa0dSJeff Roberson 
26180f86c9fSJeff Roberson #ifdef SMP
26207095abfSIvan Voras struct cpu_group *cpu_top;		/* CPU topology */
2637b8bfa0dSJeff Roberson 
26462fa74d9SJeff Roberson #define	SCHED_AFFINITY_DEFAULT	(max(1, hz / 1000))
26562fa74d9SJeff Roberson #define	SCHED_AFFINITY(ts, t)	((ts)->ts_rltick > ticks - ((t) * affinity))
2667b8bfa0dSJeff Roberson 
2677b8bfa0dSJeff Roberson /*
2687b8bfa0dSJeff Roberson  * Run-time tunables.
2697b8bfa0dSJeff Roberson  */
27028994a58SJeff Roberson static int rebalance = 1;
2717fcf154aSJeff Roberson static int balance_interval = 128;	/* Default set in sched_initticks(). */
2727b8bfa0dSJeff Roberson static int affinity;
27328994a58SJeff Roberson static int steal_idle = 1;
27428994a58SJeff Roberson static int steal_thresh = 2;
27580f86c9fSJeff Roberson 
27635e6168fSJeff Roberson /*
277d2ad694cSJeff Roberson  * One thread queue per processor.
27835e6168fSJeff Roberson  */
279ad1e7d28SJulian Elischer static struct tdq	tdq_cpu[MAXCPU];
2807fcf154aSJeff Roberson static struct tdq	*balance_tdq;
2817fcf154aSJeff Roberson static int balance_ticks;
28236acfc65SAlexander Motin static DPCPU_DEFINE(uint32_t, randomval);
283dc03363dSJeff Roberson 
284ad1e7d28SJulian Elischer #define	TDQ_SELF()	(&tdq_cpu[PCPU_GET(cpuid)])
285ad1e7d28SJulian Elischer #define	TDQ_CPU(x)	(&tdq_cpu[(x)])
286c47f202bSJeff Roberson #define	TDQ_ID(x)	((int)((x) - tdq_cpu))
28780f86c9fSJeff Roberson #else	/* !SMP */
288ad1e7d28SJulian Elischer static struct tdq	tdq_cpu;
289dc03363dSJeff Roberson 
29036b36916SJeff Roberson #define	TDQ_ID(x)	(0)
291ad1e7d28SJulian Elischer #define	TDQ_SELF()	(&tdq_cpu)
292ad1e7d28SJulian Elischer #define	TDQ_CPU(x)	(&tdq_cpu)
2930a016a05SJeff Roberson #endif
29435e6168fSJeff Roberson 
295ae7a6b38SJeff Roberson #define	TDQ_LOCK_ASSERT(t, type)	mtx_assert(TDQ_LOCKPTR((t)), (type))
296ae7a6b38SJeff Roberson #define	TDQ_LOCK(t)		mtx_lock_spin(TDQ_LOCKPTR((t)))
297ae7a6b38SJeff Roberson #define	TDQ_LOCK_FLAGS(t, f)	mtx_lock_spin_flags(TDQ_LOCKPTR((t)), (f))
298ae7a6b38SJeff Roberson #define	TDQ_UNLOCK(t)		mtx_unlock_spin(TDQ_LOCKPTR((t)))
2994ceaf45dSAttilio Rao #define	TDQ_LOCKPTR(t)		((struct mtx *)(&(t)->tdq_lock))
300ae7a6b38SJeff Roberson 
3018460a577SJohn Birrell static void sched_priority(struct thread *);
30221381d1bSJeff Roberson static void sched_thread_priority(struct thread *, u_char);
3038460a577SJohn Birrell static int sched_interact_score(struct thread *);
3048460a577SJohn Birrell static void sched_interact_update(struct thread *);
3058460a577SJohn Birrell static void sched_interact_fork(struct thread *);
3067295465eSAlexander Motin static void sched_pctcpu_update(struct td_sched *, int);
30735e6168fSJeff Roberson 
3085d7ef00cSJeff Roberson /* Operations on per processor queues */
3099727e637SJeff Roberson static struct thread *tdq_choose(struct tdq *);
310ad1e7d28SJulian Elischer static void tdq_setup(struct tdq *);
3119727e637SJeff Roberson static void tdq_load_add(struct tdq *, struct thread *);
3129727e637SJeff Roberson static void tdq_load_rem(struct tdq *, struct thread *);
3139727e637SJeff Roberson static __inline void tdq_runq_add(struct tdq *, struct thread *, int);
3149727e637SJeff Roberson static __inline void tdq_runq_rem(struct tdq *, struct thread *);
315ff256d9cSJeff Roberson static inline int sched_shouldpreempt(int, int, int);
316ad1e7d28SJulian Elischer void tdq_print(int cpu);
317e7d50326SJeff Roberson static void runq_print(struct runq *rq);
318ae7a6b38SJeff Roberson static void tdq_add(struct tdq *, struct thread *, int);
3195d7ef00cSJeff Roberson #ifdef SMP
32062fa74d9SJeff Roberson static int tdq_move(struct tdq *, struct tdq *);
321ad1e7d28SJulian Elischer static int tdq_idled(struct tdq *);
32227ee18adSRyan Stone static void tdq_notify(struct tdq *, struct thread *);
3239727e637SJeff Roberson static struct thread *tdq_steal(struct tdq *, int);
3249727e637SJeff Roberson static struct thread *runq_steal(struct runq *, int);
3259727e637SJeff Roberson static int sched_pickcpu(struct thread *, int);
3267fcf154aSJeff Roberson static void sched_balance(void);
32762fa74d9SJeff Roberson static int sched_balance_pair(struct tdq *, struct tdq *);
3289727e637SJeff Roberson static inline struct tdq *sched_setcpu(struct thread *, int, int);
329ae7a6b38SJeff Roberson static inline void thread_unblock_switch(struct thread *, struct mtx *);
330c47f202bSJeff Roberson static struct mtx *sched_switch_migrate(struct tdq *, struct thread *, int);
33107095abfSIvan Voras static int sysctl_kern_sched_topology_spec(SYSCTL_HANDLER_ARGS);
33207095abfSIvan Voras static int sysctl_kern_sched_topology_spec_internal(struct sbuf *sb,
33307095abfSIvan Voras     struct cpu_group *cg, int indent);
3345d7ef00cSJeff Roberson #endif
3355d7ef00cSJeff Roberson 
336e7d50326SJeff Roberson static void sched_setup(void *dummy);
337237fdd78SRobert Watson SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL);
338e7d50326SJeff Roberson 
339e7d50326SJeff Roberson static void sched_initticks(void *dummy);
340237fdd78SRobert Watson SYSINIT(sched_initticks, SI_SUB_CLOCKS, SI_ORDER_THIRD, sched_initticks,
341237fdd78SRobert Watson     NULL);
342e7d50326SJeff Roberson 
343b3e9e682SRyan Stone SDT_PROVIDER_DEFINE(sched);
344b3e9e682SRyan Stone 
345d9fae5abSAndriy Gapon SDT_PROBE_DEFINE3(sched, , , change__pri, "struct thread *",
346b3e9e682SRyan Stone     "struct proc *", "uint8_t");
347d9fae5abSAndriy Gapon SDT_PROBE_DEFINE3(sched, , , dequeue, "struct thread *",
348b3e9e682SRyan Stone     "struct proc *", "void *");
349d9fae5abSAndriy Gapon SDT_PROBE_DEFINE4(sched, , , enqueue, "struct thread *",
350b3e9e682SRyan Stone     "struct proc *", "void *", "int");
351d9fae5abSAndriy Gapon SDT_PROBE_DEFINE4(sched, , , lend__pri, "struct thread *",
352b3e9e682SRyan Stone     "struct proc *", "uint8_t", "struct thread *");
353d9fae5abSAndriy Gapon SDT_PROBE_DEFINE2(sched, , , load__change, "int", "int");
354d9fae5abSAndriy Gapon SDT_PROBE_DEFINE2(sched, , , off__cpu, "struct thread *",
355b3e9e682SRyan Stone     "struct proc *");
356d9fae5abSAndriy Gapon SDT_PROBE_DEFINE(sched, , , on__cpu);
357d9fae5abSAndriy Gapon SDT_PROBE_DEFINE(sched, , , remain__cpu);
358d9fae5abSAndriy Gapon SDT_PROBE_DEFINE2(sched, , , surrender, "struct thread *",
359b3e9e682SRyan Stone     "struct proc *");
360b3e9e682SRyan Stone 
3610567b6ccSWarner Losh /*
362ae7a6b38SJeff Roberson  * Print the threads waiting on a run-queue.
363ae7a6b38SJeff Roberson  */
364e7d50326SJeff Roberson static void
365e7d50326SJeff Roberson runq_print(struct runq *rq)
366e7d50326SJeff Roberson {
367e7d50326SJeff Roberson 	struct rqhead *rqh;
3689727e637SJeff Roberson 	struct thread *td;
369e7d50326SJeff Roberson 	int pri;
370e7d50326SJeff Roberson 	int j;
371e7d50326SJeff Roberson 	int i;
372e7d50326SJeff Roberson 
373e7d50326SJeff Roberson 	for (i = 0; i < RQB_LEN; i++) {
374e7d50326SJeff Roberson 		printf("\t\trunq bits %d 0x%zx\n",
375e7d50326SJeff Roberson 		    i, rq->rq_status.rqb_bits[i]);
376e7d50326SJeff Roberson 		for (j = 0; j < RQB_BPW; j++)
377e7d50326SJeff Roberson 			if (rq->rq_status.rqb_bits[i] & (1ul << j)) {
378e7d50326SJeff Roberson 				pri = j + (i << RQB_L2BPW);
379e7d50326SJeff Roberson 				rqh = &rq->rq_queues[pri];
3809727e637SJeff Roberson 				TAILQ_FOREACH(td, rqh, td_runq) {
381e7d50326SJeff Roberson 					printf("\t\t\ttd %p(%s) priority %d rqindex %d pri %d\n",
3829727e637SJeff Roberson 					    td, td->td_name, td->td_priority,
3839727e637SJeff Roberson 					    td->td_rqindex, pri);
384e7d50326SJeff Roberson 				}
385e7d50326SJeff Roberson 			}
386e7d50326SJeff Roberson 	}
387e7d50326SJeff Roberson }
388e7d50326SJeff Roberson 
389ae7a6b38SJeff Roberson /*
390ae7a6b38SJeff Roberson  * Print the status of a per-cpu thread queue.  Should be a ddb show cmd.
391ae7a6b38SJeff Roberson  */
39215dc847eSJeff Roberson void
393ad1e7d28SJulian Elischer tdq_print(int cpu)
39415dc847eSJeff Roberson {
395ad1e7d28SJulian Elischer 	struct tdq *tdq;
39615dc847eSJeff Roberson 
397ad1e7d28SJulian Elischer 	tdq = TDQ_CPU(cpu);
39815dc847eSJeff Roberson 
399c47f202bSJeff Roberson 	printf("tdq %d:\n", TDQ_ID(tdq));
40062fa74d9SJeff Roberson 	printf("\tlock            %p\n", TDQ_LOCKPTR(tdq));
40162fa74d9SJeff Roberson 	printf("\tLock name:      %s\n", tdq->tdq_name);
402d2ad694cSJeff Roberson 	printf("\tload:           %d\n", tdq->tdq_load);
4031690c6c1SJeff Roberson 	printf("\tswitch cnt:     %d\n", tdq->tdq_switchcnt);
4041690c6c1SJeff Roberson 	printf("\told switch cnt: %d\n", tdq->tdq_oldswitchcnt);
405e7d50326SJeff Roberson 	printf("\ttimeshare idx:  %d\n", tdq->tdq_idx);
4063f872f85SJeff Roberson 	printf("\ttimeshare ridx: %d\n", tdq->tdq_ridx);
4071690c6c1SJeff Roberson 	printf("\tload transferable: %d\n", tdq->tdq_transferable);
4081690c6c1SJeff Roberson 	printf("\tlowest priority:   %d\n", tdq->tdq_lowpri);
409e7d50326SJeff Roberson 	printf("\trealtime runq:\n");
410e7d50326SJeff Roberson 	runq_print(&tdq->tdq_realtime);
411e7d50326SJeff Roberson 	printf("\ttimeshare runq:\n");
412e7d50326SJeff Roberson 	runq_print(&tdq->tdq_timeshare);
413e7d50326SJeff Roberson 	printf("\tidle runq:\n");
414e7d50326SJeff Roberson 	runq_print(&tdq->tdq_idle);
41515dc847eSJeff Roberson }
41615dc847eSJeff Roberson 
417ff256d9cSJeff Roberson static inline int
418ff256d9cSJeff Roberson sched_shouldpreempt(int pri, int cpri, int remote)
419ff256d9cSJeff Roberson {
420ff256d9cSJeff Roberson 	/*
421ff256d9cSJeff Roberson 	 * If the new priority is not better than the current priority there is
422ff256d9cSJeff Roberson 	 * nothing to do.
423ff256d9cSJeff Roberson 	 */
424ff256d9cSJeff Roberson 	if (pri >= cpri)
425ff256d9cSJeff Roberson 		return (0);
426ff256d9cSJeff Roberson 	/*
427ff256d9cSJeff Roberson 	 * Always preempt idle.
428ff256d9cSJeff Roberson 	 */
429ff256d9cSJeff Roberson 	if (cpri >= PRI_MIN_IDLE)
430ff256d9cSJeff Roberson 		return (1);
431ff256d9cSJeff Roberson 	/*
432ff256d9cSJeff Roberson 	 * If preemption is disabled don't preempt others.
433ff256d9cSJeff Roberson 	 */
434ff256d9cSJeff Roberson 	if (preempt_thresh == 0)
435ff256d9cSJeff Roberson 		return (0);
436ff256d9cSJeff Roberson 	/*
437ff256d9cSJeff Roberson 	 * Preempt if we exceed the threshold.
438ff256d9cSJeff Roberson 	 */
439ff256d9cSJeff Roberson 	if (pri <= preempt_thresh)
440ff256d9cSJeff Roberson 		return (1);
441ff256d9cSJeff Roberson 	/*
44212d56c0fSJohn Baldwin 	 * If we're interactive or better and there is non-interactive
44312d56c0fSJohn Baldwin 	 * or worse running preempt only remote processors.
444ff256d9cSJeff Roberson 	 */
44512d56c0fSJohn Baldwin 	if (remote && pri <= PRI_MAX_INTERACT && cpri > PRI_MAX_INTERACT)
446ff256d9cSJeff Roberson 		return (1);
447ff256d9cSJeff Roberson 	return (0);
448ff256d9cSJeff Roberson }
449ff256d9cSJeff Roberson 
450ae7a6b38SJeff Roberson /*
451ae7a6b38SJeff Roberson  * Add a thread to the actual run-queue.  Keeps transferable counts up to
452ae7a6b38SJeff Roberson  * date with what is actually on the run-queue.  Selects the correct
453ae7a6b38SJeff Roberson  * queue position for timeshare threads.
454ae7a6b38SJeff Roberson  */
455155b9987SJeff Roberson static __inline void
4569727e637SJeff Roberson tdq_runq_add(struct tdq *tdq, struct thread *td, int flags)
457155b9987SJeff Roberson {
4589727e637SJeff Roberson 	struct td_sched *ts;
459c143ac21SJeff Roberson 	u_char pri;
460c143ac21SJeff Roberson 
461ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
4629727e637SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
46373daf66fSJeff Roberson 
4649727e637SJeff Roberson 	pri = td->td_priority;
46593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
4669727e637SJeff Roberson 	TD_SET_RUNQ(td);
4679727e637SJeff Roberson 	if (THREAD_CAN_MIGRATE(td)) {
468d2ad694cSJeff Roberson 		tdq->tdq_transferable++;
469ad1e7d28SJulian Elischer 		ts->ts_flags |= TSF_XFERABLE;
47080f86c9fSJeff Roberson 	}
47112d56c0fSJohn Baldwin 	if (pri < PRI_MIN_BATCH) {
472c143ac21SJeff Roberson 		ts->ts_runq = &tdq->tdq_realtime;
47312d56c0fSJohn Baldwin 	} else if (pri <= PRI_MAX_BATCH) {
474c143ac21SJeff Roberson 		ts->ts_runq = &tdq->tdq_timeshare;
47512d56c0fSJohn Baldwin 		KASSERT(pri <= PRI_MAX_BATCH && pri >= PRI_MIN_BATCH,
476e7d50326SJeff Roberson 			("Invalid priority %d on timeshare runq", pri));
477e7d50326SJeff Roberson 		/*
478e7d50326SJeff Roberson 		 * This queue contains only priorities between MIN and MAX
479e7d50326SJeff Roberson 		 * realtime.  Use the whole queue to represent these values.
480e7d50326SJeff Roberson 		 */
481c47f202bSJeff Roberson 		if ((flags & (SRQ_BORROWING|SRQ_PREEMPTED)) == 0) {
48216705791SAndriy Gapon 			pri = RQ_NQS * (pri - PRI_MIN_BATCH) / PRI_BATCH_RANGE;
483e7d50326SJeff Roberson 			pri = (pri + tdq->tdq_idx) % RQ_NQS;
4843f872f85SJeff Roberson 			/*
4853f872f85SJeff Roberson 			 * This effectively shortens the queue by one so we
4863f872f85SJeff Roberson 			 * can have a one slot difference between idx and
4873f872f85SJeff Roberson 			 * ridx while we wait for threads to drain.
4883f872f85SJeff Roberson 			 */
4893f872f85SJeff Roberson 			if (tdq->tdq_ridx != tdq->tdq_idx &&
4903f872f85SJeff Roberson 			    pri == tdq->tdq_ridx)
4914499aff6SJeff Roberson 				pri = (unsigned char)(pri - 1) % RQ_NQS;
492e7d50326SJeff Roberson 		} else
4933f872f85SJeff Roberson 			pri = tdq->tdq_ridx;
4949727e637SJeff Roberson 		runq_add_pri(ts->ts_runq, td, pri, flags);
495c143ac21SJeff Roberson 		return;
496e7d50326SJeff Roberson 	} else
49773daf66fSJeff Roberson 		ts->ts_runq = &tdq->tdq_idle;
4989727e637SJeff Roberson 	runq_add(ts->ts_runq, td, flags);
49973daf66fSJeff Roberson }
50073daf66fSJeff Roberson 
50173daf66fSJeff Roberson /*
502ae7a6b38SJeff Roberson  * Remove a thread from a run-queue.  This typically happens when a thread
503ae7a6b38SJeff Roberson  * is selected to run.  Running threads are not on the queue and the
504ae7a6b38SJeff Roberson  * transferable count does not reflect them.
505ae7a6b38SJeff Roberson  */
506155b9987SJeff Roberson static __inline void
5079727e637SJeff Roberson tdq_runq_rem(struct tdq *tdq, struct thread *td)
508155b9987SJeff Roberson {
5099727e637SJeff Roberson 	struct td_sched *ts;
5109727e637SJeff Roberson 
51193ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
512ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
513ae7a6b38SJeff Roberson 	KASSERT(ts->ts_runq != NULL,
5149727e637SJeff Roberson 	    ("tdq_runq_remove: thread %p null ts_runq", td));
515ad1e7d28SJulian Elischer 	if (ts->ts_flags & TSF_XFERABLE) {
516d2ad694cSJeff Roberson 		tdq->tdq_transferable--;
517ad1e7d28SJulian Elischer 		ts->ts_flags &= ~TSF_XFERABLE;
51880f86c9fSJeff Roberson 	}
5193f872f85SJeff Roberson 	if (ts->ts_runq == &tdq->tdq_timeshare) {
5203f872f85SJeff Roberson 		if (tdq->tdq_idx != tdq->tdq_ridx)
5219727e637SJeff Roberson 			runq_remove_idx(ts->ts_runq, td, &tdq->tdq_ridx);
522e7d50326SJeff Roberson 		else
5239727e637SJeff Roberson 			runq_remove_idx(ts->ts_runq, td, NULL);
5243f872f85SJeff Roberson 	} else
5259727e637SJeff Roberson 		runq_remove(ts->ts_runq, td);
526155b9987SJeff Roberson }
527155b9987SJeff Roberson 
528ae7a6b38SJeff Roberson /*
529ae7a6b38SJeff Roberson  * Load is maintained for all threads RUNNING and ON_RUNQ.  Add the load
530ae7a6b38SJeff Roberson  * for this thread to the referenced thread queue.
531ae7a6b38SJeff Roberson  */
532a8949de2SJeff Roberson static void
5339727e637SJeff Roberson tdq_load_add(struct tdq *tdq, struct thread *td)
5345d7ef00cSJeff Roberson {
535ae7a6b38SJeff Roberson 
536ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
5379727e637SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
53803d17db7SJeff Roberson 
539d2ad694cSJeff Roberson 	tdq->tdq_load++;
5401b9d701fSAttilio Rao 	if ((td->td_flags & TDF_NOLOAD) == 0)
541d2ad694cSJeff Roberson 		tdq->tdq_sysload++;
5428f51ad55SJeff Roberson 	KTR_COUNTER0(KTR_SCHED, "load", tdq->tdq_loadname, tdq->tdq_load);
543d9fae5abSAndriy Gapon 	SDT_PROBE2(sched, , , load__change, (int)TDQ_ID(tdq), tdq->tdq_load);
5445d7ef00cSJeff Roberson }
54515dc847eSJeff Roberson 
546ae7a6b38SJeff Roberson /*
547ae7a6b38SJeff Roberson  * Remove the load from a thread that is transitioning to a sleep state or
548ae7a6b38SJeff Roberson  * exiting.
549ae7a6b38SJeff Roberson  */
550a8949de2SJeff Roberson static void
5519727e637SJeff Roberson tdq_load_rem(struct tdq *tdq, struct thread *td)
5525d7ef00cSJeff Roberson {
553ae7a6b38SJeff Roberson 
5549727e637SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
555ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
556ae7a6b38SJeff Roberson 	KASSERT(tdq->tdq_load != 0,
557c47f202bSJeff Roberson 	    ("tdq_load_rem: Removing with 0 load on queue %d", TDQ_ID(tdq)));
55803d17db7SJeff Roberson 
559d2ad694cSJeff Roberson 	tdq->tdq_load--;
5601b9d701fSAttilio Rao 	if ((td->td_flags & TDF_NOLOAD) == 0)
56103d17db7SJeff Roberson 		tdq->tdq_sysload--;
5628f51ad55SJeff Roberson 	KTR_COUNTER0(KTR_SCHED, "load", tdq->tdq_loadname, tdq->tdq_load);
563d9fae5abSAndriy Gapon 	SDT_PROBE2(sched, , , load__change, (int)TDQ_ID(tdq), tdq->tdq_load);
56415dc847eSJeff Roberson }
56515dc847eSJeff Roberson 
566356500a3SJeff Roberson /*
5675e5c3873SJeff Roberson  * Bound timeshare latency by decreasing slice size as load increases.  We
5685e5c3873SJeff Roberson  * consider the maximum latency as the sum of the threads waiting to run
5695e5c3873SJeff Roberson  * aside from curthread and target no more than sched_slice latency but
5705e5c3873SJeff Roberson  * no less than sched_slice_min runtime.
5715e5c3873SJeff Roberson  */
5725e5c3873SJeff Roberson static inline int
5735e5c3873SJeff Roberson tdq_slice(struct tdq *tdq)
5745e5c3873SJeff Roberson {
5755e5c3873SJeff Roberson 	int load;
5765e5c3873SJeff Roberson 
5775e5c3873SJeff Roberson 	/*
5785e5c3873SJeff Roberson 	 * It is safe to use sys_load here because this is called from
5795e5c3873SJeff Roberson 	 * contexts where timeshare threads are running and so there
5805e5c3873SJeff Roberson 	 * cannot be higher priority load in the system.
5815e5c3873SJeff Roberson 	 */
5825e5c3873SJeff Roberson 	load = tdq->tdq_sysload - 1;
5835e5c3873SJeff Roberson 	if (load >= SCHED_SLICE_MIN_DIVISOR)
5845e5c3873SJeff Roberson 		return (sched_slice_min);
5855e5c3873SJeff Roberson 	if (load <= 1)
5865e5c3873SJeff Roberson 		return (sched_slice);
5875e5c3873SJeff Roberson 	return (sched_slice / load);
5885e5c3873SJeff Roberson }
5895e5c3873SJeff Roberson 
5905e5c3873SJeff Roberson /*
59162fa74d9SJeff Roberson  * Set lowpri to its exact value by searching the run-queue and
59262fa74d9SJeff Roberson  * evaluating curthread.  curthread may be passed as an optimization.
593356500a3SJeff Roberson  */
59422bf7d9aSJeff Roberson static void
59562fa74d9SJeff Roberson tdq_setlowpri(struct tdq *tdq, struct thread *ctd)
59662fa74d9SJeff Roberson {
59762fa74d9SJeff Roberson 	struct thread *td;
59862fa74d9SJeff Roberson 
59962fa74d9SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
60062fa74d9SJeff Roberson 	if (ctd == NULL)
60162fa74d9SJeff Roberson 		ctd = pcpu_find(TDQ_ID(tdq))->pc_curthread;
6029727e637SJeff Roberson 	td = tdq_choose(tdq);
6039727e637SJeff Roberson 	if (td == NULL || td->td_priority > ctd->td_priority)
60462fa74d9SJeff Roberson 		tdq->tdq_lowpri = ctd->td_priority;
60562fa74d9SJeff Roberson 	else
60662fa74d9SJeff Roberson 		tdq->tdq_lowpri = td->td_priority;
60762fa74d9SJeff Roberson }
60862fa74d9SJeff Roberson 
60962fa74d9SJeff Roberson #ifdef SMP
6109129dd59SPedro F. Giffuni /*
6119129dd59SPedro F. Giffuni  * We need some randomness. Implement a classic Linear Congruential
6129129dd59SPedro F. Giffuni  * Generator X_{n+1}=(aX_n+c) mod m. These values are optimized for
6139129dd59SPedro F. Giffuni  * m = 2^32, a = 69069 and c = 5. We only return the upper 16 bits
6149129dd59SPedro F. Giffuni  * of the random state (in the low bits of our answer) to keep
6159129dd59SPedro F. Giffuni  * the maximum randomness.
6169129dd59SPedro F. Giffuni  */
6179129dd59SPedro F. Giffuni static uint32_t
6189129dd59SPedro F. Giffuni sched_random(void)
6199129dd59SPedro F. Giffuni {
6209129dd59SPedro F. Giffuni 	uint32_t *rndptr;
6219129dd59SPedro F. Giffuni 
6229129dd59SPedro F. Giffuni 	rndptr = DPCPU_PTR(randomval);
6239129dd59SPedro F. Giffuni 	*rndptr = *rndptr * 69069 + 5;
6249129dd59SPedro F. Giffuni 
6259129dd59SPedro F. Giffuni 	return (*rndptr >> 16);
6269129dd59SPedro F. Giffuni }
6279129dd59SPedro F. Giffuni 
62862fa74d9SJeff Roberson struct cpu_search {
629c76ee827SJeff Roberson 	cpuset_t cs_mask;
63036acfc65SAlexander Motin 	u_int	cs_prefer;
63136acfc65SAlexander Motin 	int	cs_pri;		/* Min priority for low. */
63236acfc65SAlexander Motin 	int	cs_limit;	/* Max load for low, min load for high. */
63336acfc65SAlexander Motin 	int	cs_cpu;
63436acfc65SAlexander Motin 	int	cs_load;
63562fa74d9SJeff Roberson };
63662fa74d9SJeff Roberson 
63762fa74d9SJeff Roberson #define	CPU_SEARCH_LOWEST	0x1
63862fa74d9SJeff Roberson #define	CPU_SEARCH_HIGHEST	0x2
63962fa74d9SJeff Roberson #define	CPU_SEARCH_BOTH		(CPU_SEARCH_LOWEST|CPU_SEARCH_HIGHEST)
64062fa74d9SJeff Roberson 
641c76ee827SJeff Roberson #define	CPUSET_FOREACH(cpu, mask)				\
642c76ee827SJeff Roberson 	for ((cpu) = 0; (cpu) <= mp_maxid; (cpu)++)		\
64371a19bdcSAttilio Rao 		if (CPU_ISSET(cpu, &mask))
64462fa74d9SJeff Roberson 
6452499a5ccSKonstantin Belousov static __always_inline int cpu_search(const struct cpu_group *cg,
6462499a5ccSKonstantin Belousov     struct cpu_search *low, struct cpu_search *high, const int match);
6472499a5ccSKonstantin Belousov int __noinline cpu_search_lowest(const struct cpu_group *cg,
6482499a5ccSKonstantin Belousov     struct cpu_search *low);
6492499a5ccSKonstantin Belousov int __noinline cpu_search_highest(const struct cpu_group *cg,
65062fa74d9SJeff Roberson     struct cpu_search *high);
6512499a5ccSKonstantin Belousov int __noinline cpu_search_both(const struct cpu_group *cg,
6522499a5ccSKonstantin Belousov     struct cpu_search *low, struct cpu_search *high);
65362fa74d9SJeff Roberson 
65462fa74d9SJeff Roberson /*
65562fa74d9SJeff Roberson  * Search the tree of cpu_groups for the lowest or highest loaded cpu
65662fa74d9SJeff Roberson  * according to the match argument.  This routine actually compares the
65762fa74d9SJeff Roberson  * load on all paths through the tree and finds the least loaded cpu on
65862fa74d9SJeff Roberson  * the least loaded path, which may differ from the least loaded cpu in
659db4fcadfSConrad Meyer  * the system.  This balances work among caches and buses.
66062fa74d9SJeff Roberson  *
66162fa74d9SJeff Roberson  * This inline is instantiated in three forms below using constants for the
66262fa74d9SJeff Roberson  * match argument.  It is reduced to the minimum set for each case.  It is
66362fa74d9SJeff Roberson  * also recursive to the depth of the tree.
66462fa74d9SJeff Roberson  */
6652499a5ccSKonstantin Belousov static __always_inline int
66636acfc65SAlexander Motin cpu_search(const struct cpu_group *cg, struct cpu_search *low,
66762fa74d9SJeff Roberson     struct cpu_search *high, const int match)
66862fa74d9SJeff Roberson {
66962fa74d9SJeff Roberson 	struct cpu_search lgroup;
67062fa74d9SJeff Roberson 	struct cpu_search hgroup;
67136acfc65SAlexander Motin 	cpuset_t cpumask;
67262fa74d9SJeff Roberson 	struct cpu_group *child;
67336acfc65SAlexander Motin 	struct tdq *tdq;
6740567b6ccSWarner Losh 	int cpu, i, hload, lload, load, total, rnd;
67562fa74d9SJeff Roberson 
67636acfc65SAlexander Motin 	total = 0;
67736acfc65SAlexander Motin 	cpumask = cg->cg_mask;
67862fa74d9SJeff Roberson 	if (match & CPU_SEARCH_LOWEST) {
67936acfc65SAlexander Motin 		lload = INT_MAX;
68062fa74d9SJeff Roberson 		lgroup = *low;
68162fa74d9SJeff Roberson 	}
68262fa74d9SJeff Roberson 	if (match & CPU_SEARCH_HIGHEST) {
68370801abeSAlexander Motin 		hload = INT_MIN;
68462fa74d9SJeff Roberson 		hgroup = *high;
68562fa74d9SJeff Roberson 	}
68636acfc65SAlexander Motin 
68736acfc65SAlexander Motin 	/* Iterate through the child CPU groups and then remaining CPUs. */
68858909b74SAlexander Motin 	for (i = cg->cg_children, cpu = mp_maxid; ; ) {
68970801abeSAlexander Motin 		if (i == 0) {
69058909b74SAlexander Motin #ifdef HAVE_INLINE_FFSL
69158909b74SAlexander Motin 			cpu = CPU_FFS(&cpumask) - 1;
69258909b74SAlexander Motin #else
69370801abeSAlexander Motin 			while (cpu >= 0 && !CPU_ISSET(cpu, &cpumask))
69470801abeSAlexander Motin 				cpu--;
69558909b74SAlexander Motin #endif
69670801abeSAlexander Motin 			if (cpu < 0)
69736acfc65SAlexander Motin 				break;
69836acfc65SAlexander Motin 			child = NULL;
69936acfc65SAlexander Motin 		} else
70070801abeSAlexander Motin 			child = &cg->cg_child[i - 1];
70136acfc65SAlexander Motin 
70270801abeSAlexander Motin 		if (match & CPU_SEARCH_LOWEST)
70370801abeSAlexander Motin 			lgroup.cs_cpu = -1;
70470801abeSAlexander Motin 		if (match & CPU_SEARCH_HIGHEST)
70570801abeSAlexander Motin 			hgroup.cs_cpu = -1;
70636acfc65SAlexander Motin 		if (child) {			/* Handle child CPU group. */
70736acfc65SAlexander Motin 			CPU_NAND(&cpumask, &child->cg_mask);
70862fa74d9SJeff Roberson 			switch (match) {
70962fa74d9SJeff Roberson 			case CPU_SEARCH_LOWEST:
71062fa74d9SJeff Roberson 				load = cpu_search_lowest(child, &lgroup);
71162fa74d9SJeff Roberson 				break;
71262fa74d9SJeff Roberson 			case CPU_SEARCH_HIGHEST:
71362fa74d9SJeff Roberson 				load = cpu_search_highest(child, &hgroup);
71462fa74d9SJeff Roberson 				break;
71562fa74d9SJeff Roberson 			case CPU_SEARCH_BOTH:
71662fa74d9SJeff Roberson 				load = cpu_search_both(child, &lgroup, &hgroup);
71762fa74d9SJeff Roberson 				break;
71862fa74d9SJeff Roberson 			}
71936acfc65SAlexander Motin 		} else {			/* Handle child CPU. */
72058909b74SAlexander Motin 			CPU_CLR(cpu, &cpumask);
72136acfc65SAlexander Motin 			tdq = TDQ_CPU(cpu);
72236acfc65SAlexander Motin 			load = tdq->tdq_load * 256;
723b250ad34SWarner Losh 			rnd = sched_random() % 32;
72436acfc65SAlexander Motin 			if (match & CPU_SEARCH_LOWEST) {
72536acfc65SAlexander Motin 				if (cpu == low->cs_prefer)
72636acfc65SAlexander Motin 					load -= 64;
72736acfc65SAlexander Motin 				/* If that CPU is allowed and get data. */
72870801abeSAlexander Motin 				if (tdq->tdq_lowpri > lgroup.cs_pri &&
72970801abeSAlexander Motin 				    tdq->tdq_load <= lgroup.cs_limit &&
73070801abeSAlexander Motin 				    CPU_ISSET(cpu, &lgroup.cs_mask)) {
73136acfc65SAlexander Motin 					lgroup.cs_cpu = cpu;
73236acfc65SAlexander Motin 					lgroup.cs_load = load - rnd;
73336acfc65SAlexander Motin 				}
73462fa74d9SJeff Roberson 			}
73562fa74d9SJeff Roberson 			if (match & CPU_SEARCH_HIGHEST)
73670801abeSAlexander Motin 				if (tdq->tdq_load >= hgroup.cs_limit &&
73770801abeSAlexander Motin 				    tdq->tdq_transferable &&
73870801abeSAlexander Motin 				    CPU_ISSET(cpu, &hgroup.cs_mask)) {
73936acfc65SAlexander Motin 					hgroup.cs_cpu = cpu;
74036acfc65SAlexander Motin 					hgroup.cs_load = load - rnd;
74162fa74d9SJeff Roberson 				}
74262fa74d9SJeff Roberson 		}
74336acfc65SAlexander Motin 		total += load;
74462fa74d9SJeff Roberson 
74536acfc65SAlexander Motin 		/* We have info about child item. Compare it. */
74636acfc65SAlexander Motin 		if (match & CPU_SEARCH_LOWEST) {
74770801abeSAlexander Motin 			if (lgroup.cs_cpu >= 0 &&
7486022f0bcSAlexander Motin 			    (load < lload ||
7496022f0bcSAlexander Motin 			     (load == lload && lgroup.cs_load < low->cs_load))) {
75036acfc65SAlexander Motin 				lload = load;
75136acfc65SAlexander Motin 				low->cs_cpu = lgroup.cs_cpu;
75236acfc65SAlexander Motin 				low->cs_load = lgroup.cs_load;
75336acfc65SAlexander Motin 			}
75436acfc65SAlexander Motin 		}
75536acfc65SAlexander Motin 		if (match & CPU_SEARCH_HIGHEST)
75670801abeSAlexander Motin 			if (hgroup.cs_cpu >= 0 &&
7576022f0bcSAlexander Motin 			    (load > hload ||
7586022f0bcSAlexander Motin 			     (load == hload && hgroup.cs_load > high->cs_load))) {
75936acfc65SAlexander Motin 				hload = load;
76036acfc65SAlexander Motin 				high->cs_cpu = hgroup.cs_cpu;
76136acfc65SAlexander Motin 				high->cs_load = hgroup.cs_load;
76236acfc65SAlexander Motin 			}
76370801abeSAlexander Motin 		if (child) {
76470801abeSAlexander Motin 			i--;
76570801abeSAlexander Motin 			if (i == 0 && CPU_EMPTY(&cpumask))
76670801abeSAlexander Motin 				break;
76758909b74SAlexander Motin 		}
76858909b74SAlexander Motin #ifndef HAVE_INLINE_FFSL
76958909b74SAlexander Motin 		else
77070801abeSAlexander Motin 			cpu--;
77158909b74SAlexander Motin #endif
77262fa74d9SJeff Roberson 	}
77362fa74d9SJeff Roberson 	return (total);
77462fa74d9SJeff Roberson }
77562fa74d9SJeff Roberson 
77662fa74d9SJeff Roberson /*
77762fa74d9SJeff Roberson  * cpu_search instantiations must pass constants to maintain the inline
77862fa74d9SJeff Roberson  * optimization.
77962fa74d9SJeff Roberson  */
78062fa74d9SJeff Roberson int
78136acfc65SAlexander Motin cpu_search_lowest(const struct cpu_group *cg, struct cpu_search *low)
78262fa74d9SJeff Roberson {
78362fa74d9SJeff Roberson 	return cpu_search(cg, low, NULL, CPU_SEARCH_LOWEST);
78462fa74d9SJeff Roberson }
78562fa74d9SJeff Roberson 
78662fa74d9SJeff Roberson int
78736acfc65SAlexander Motin cpu_search_highest(const struct cpu_group *cg, struct cpu_search *high)
78862fa74d9SJeff Roberson {
78962fa74d9SJeff Roberson 	return cpu_search(cg, NULL, high, CPU_SEARCH_HIGHEST);
79062fa74d9SJeff Roberson }
79162fa74d9SJeff Roberson 
79262fa74d9SJeff Roberson int
79336acfc65SAlexander Motin cpu_search_both(const struct cpu_group *cg, struct cpu_search *low,
79462fa74d9SJeff Roberson     struct cpu_search *high)
79562fa74d9SJeff Roberson {
79662fa74d9SJeff Roberson 	return cpu_search(cg, low, high, CPU_SEARCH_BOTH);
79762fa74d9SJeff Roberson }
79862fa74d9SJeff Roberson 
79962fa74d9SJeff Roberson /*
80062fa74d9SJeff Roberson  * Find the cpu with the least load via the least loaded path that has a
80162fa74d9SJeff Roberson  * lowpri greater than pri  pri.  A pri of -1 indicates any priority is
80262fa74d9SJeff Roberson  * acceptable.
80362fa74d9SJeff Roberson  */
80462fa74d9SJeff Roberson static inline int
80536acfc65SAlexander Motin sched_lowest(const struct cpu_group *cg, cpuset_t mask, int pri, int maxload,
80636acfc65SAlexander Motin     int prefer)
80762fa74d9SJeff Roberson {
80862fa74d9SJeff Roberson 	struct cpu_search low;
80962fa74d9SJeff Roberson 
81062fa74d9SJeff Roberson 	low.cs_cpu = -1;
81136acfc65SAlexander Motin 	low.cs_prefer = prefer;
81262fa74d9SJeff Roberson 	low.cs_mask = mask;
81336acfc65SAlexander Motin 	low.cs_pri = pri;
81436acfc65SAlexander Motin 	low.cs_limit = maxload;
81562fa74d9SJeff Roberson 	cpu_search_lowest(cg, &low);
81662fa74d9SJeff Roberson 	return low.cs_cpu;
81762fa74d9SJeff Roberson }
81862fa74d9SJeff Roberson 
81962fa74d9SJeff Roberson /*
82062fa74d9SJeff Roberson  * Find the cpu with the highest load via the highest loaded path.
82162fa74d9SJeff Roberson  */
82262fa74d9SJeff Roberson static inline int
82336acfc65SAlexander Motin sched_highest(const struct cpu_group *cg, cpuset_t mask, int minload)
82462fa74d9SJeff Roberson {
82562fa74d9SJeff Roberson 	struct cpu_search high;
82662fa74d9SJeff Roberson 
82762fa74d9SJeff Roberson 	high.cs_cpu = -1;
82862fa74d9SJeff Roberson 	high.cs_mask = mask;
82962fa74d9SJeff Roberson 	high.cs_limit = minload;
83062fa74d9SJeff Roberson 	cpu_search_highest(cg, &high);
83162fa74d9SJeff Roberson 	return high.cs_cpu;
83262fa74d9SJeff Roberson }
83362fa74d9SJeff Roberson 
83462fa74d9SJeff Roberson static void
83562fa74d9SJeff Roberson sched_balance_group(struct cpu_group *cg)
83662fa74d9SJeff Roberson {
83736acfc65SAlexander Motin 	cpuset_t hmask, lmask;
83836acfc65SAlexander Motin 	int high, low, anylow;
83962fa74d9SJeff Roberson 
84036acfc65SAlexander Motin 	CPU_FILL(&hmask);
84162fa74d9SJeff Roberson 	for (;;) {
84236acfc65SAlexander Motin 		high = sched_highest(cg, hmask, 1);
84336acfc65SAlexander Motin 		/* Stop if there is no more CPU with transferrable threads. */
84436acfc65SAlexander Motin 		if (high == -1)
84562fa74d9SJeff Roberson 			break;
84636acfc65SAlexander Motin 		CPU_CLR(high, &hmask);
84736acfc65SAlexander Motin 		CPU_COPY(&hmask, &lmask);
84836acfc65SAlexander Motin 		/* Stop if there is no more CPU left for low. */
84936acfc65SAlexander Motin 		if (CPU_EMPTY(&lmask))
85062fa74d9SJeff Roberson 			break;
85136acfc65SAlexander Motin 		anylow = 1;
85236acfc65SAlexander Motin nextlow:
85336acfc65SAlexander Motin 		low = sched_lowest(cg, lmask, -1,
85436acfc65SAlexander Motin 		    TDQ_CPU(high)->tdq_load - 1, high);
85536acfc65SAlexander Motin 		/* Stop if we looked well and found no less loaded CPU. */
85636acfc65SAlexander Motin 		if (anylow && low == -1)
85736acfc65SAlexander Motin 			break;
85836acfc65SAlexander Motin 		/* Go to next high if we found no less loaded CPU. */
85936acfc65SAlexander Motin 		if (low == -1)
86036acfc65SAlexander Motin 			continue;
86136acfc65SAlexander Motin 		/* Transfer thread from high to low. */
86236acfc65SAlexander Motin 		if (sched_balance_pair(TDQ_CPU(high), TDQ_CPU(low))) {
86336acfc65SAlexander Motin 			/* CPU that got thread can no longer be a donor. */
86436acfc65SAlexander Motin 			CPU_CLR(low, &hmask);
86536acfc65SAlexander Motin 		} else {
86662fa74d9SJeff Roberson 			/*
86736acfc65SAlexander Motin 			 * If failed, then there is no threads on high
86836acfc65SAlexander Motin 			 * that can run on this low. Drop low from low
86936acfc65SAlexander Motin 			 * mask and look for different one.
87062fa74d9SJeff Roberson 			 */
87136acfc65SAlexander Motin 			CPU_CLR(low, &lmask);
87236acfc65SAlexander Motin 			anylow = 0;
87336acfc65SAlexander Motin 			goto nextlow;
87462fa74d9SJeff Roberson 		}
87536acfc65SAlexander Motin 	}
87662fa74d9SJeff Roberson }
87762fa74d9SJeff Roberson 
87862fa74d9SJeff Roberson static void
87962375ca8SEd Schouten sched_balance(void)
880356500a3SJeff Roberson {
8817fcf154aSJeff Roberson 	struct tdq *tdq;
882356500a3SJeff Roberson 
883ae7a6b38SJeff Roberson 	if (smp_started == 0 || rebalance == 0)
884598b368dSJeff Roberson 		return;
8850567b6ccSWarner Losh 
8860567b6ccSWarner Losh 	balance_ticks = max(balance_interval / 2, 1) +
887b250ad34SWarner Losh 	    (sched_random() % balance_interval);
8887fcf154aSJeff Roberson 	tdq = TDQ_SELF();
8897fcf154aSJeff Roberson 	TDQ_UNLOCK(tdq);
89062fa74d9SJeff Roberson 	sched_balance_group(cpu_top);
8917fcf154aSJeff Roberson 	TDQ_LOCK(tdq);
892cac77d04SJeff Roberson }
89386f8ae96SJeff Roberson 
894ae7a6b38SJeff Roberson /*
895ae7a6b38SJeff Roberson  * Lock two thread queues using their address to maintain lock order.
896ae7a6b38SJeff Roberson  */
897ae7a6b38SJeff Roberson static void
898ae7a6b38SJeff Roberson tdq_lock_pair(struct tdq *one, struct tdq *two)
899ae7a6b38SJeff Roberson {
900ae7a6b38SJeff Roberson 	if (one < two) {
901ae7a6b38SJeff Roberson 		TDQ_LOCK(one);
902ae7a6b38SJeff Roberson 		TDQ_LOCK_FLAGS(two, MTX_DUPOK);
903ae7a6b38SJeff Roberson 	} else {
904ae7a6b38SJeff Roberson 		TDQ_LOCK(two);
905ae7a6b38SJeff Roberson 		TDQ_LOCK_FLAGS(one, MTX_DUPOK);
906ae7a6b38SJeff Roberson 	}
907ae7a6b38SJeff Roberson }
908ae7a6b38SJeff Roberson 
909ae7a6b38SJeff Roberson /*
9107fcf154aSJeff Roberson  * Unlock two thread queues.  Order is not important here.
9117fcf154aSJeff Roberson  */
9127fcf154aSJeff Roberson static void
9137fcf154aSJeff Roberson tdq_unlock_pair(struct tdq *one, struct tdq *two)
9147fcf154aSJeff Roberson {
9157fcf154aSJeff Roberson 	TDQ_UNLOCK(one);
9167fcf154aSJeff Roberson 	TDQ_UNLOCK(two);
9177fcf154aSJeff Roberson }
9187fcf154aSJeff Roberson 
9197fcf154aSJeff Roberson /*
920ae7a6b38SJeff Roberson  * Transfer load between two imbalanced thread queues.
921ae7a6b38SJeff Roberson  */
92262fa74d9SJeff Roberson static int
923ad1e7d28SJulian Elischer sched_balance_pair(struct tdq *high, struct tdq *low)
924cac77d04SJeff Roberson {
92562fa74d9SJeff Roberson 	int moved;
926880bf8b9SMarius Strobl 	int cpu;
927cac77d04SJeff Roberson 
928ae7a6b38SJeff Roberson 	tdq_lock_pair(high, low);
92962fa74d9SJeff Roberson 	moved = 0;
930155b9987SJeff Roberson 	/*
931155b9987SJeff Roberson 	 * Determine what the imbalance is and then adjust that to how many
932d2ad694cSJeff Roberson 	 * threads we actually have to give up (transferable).
933155b9987SJeff Roberson 	 */
93436acfc65SAlexander Motin 	if (high->tdq_transferable != 0 && high->tdq_load > low->tdq_load &&
93536acfc65SAlexander Motin 	    (moved = tdq_move(high, low)) > 0) {
936a5423ea3SJeff Roberson 		/*
937880bf8b9SMarius Strobl 		 * In case the target isn't the current cpu IPI it to force a
938880bf8b9SMarius Strobl 		 * reschedule with the new workload.
939a5423ea3SJeff Roberson 		 */
940880bf8b9SMarius Strobl 		cpu = TDQ_ID(low);
941880bf8b9SMarius Strobl 		if (cpu != PCPU_GET(cpuid))
942880bf8b9SMarius Strobl 			ipi_cpu(cpu, IPI_PREEMPT);
943ae7a6b38SJeff Roberson 	}
9447fcf154aSJeff Roberson 	tdq_unlock_pair(high, low);
94562fa74d9SJeff Roberson 	return (moved);
946356500a3SJeff Roberson }
947356500a3SJeff Roberson 
948ae7a6b38SJeff Roberson /*
949ae7a6b38SJeff Roberson  * Move a thread from one thread queue to another.
950ae7a6b38SJeff Roberson  */
95162fa74d9SJeff Roberson static int
952ae7a6b38SJeff Roberson tdq_move(struct tdq *from, struct tdq *to)
953356500a3SJeff Roberson {
954ad1e7d28SJulian Elischer 	struct td_sched *ts;
955ae7a6b38SJeff Roberson 	struct thread *td;
956ae7a6b38SJeff Roberson 	struct tdq *tdq;
957ae7a6b38SJeff Roberson 	int cpu;
958356500a3SJeff Roberson 
9597fcf154aSJeff Roberson 	TDQ_LOCK_ASSERT(from, MA_OWNED);
9607fcf154aSJeff Roberson 	TDQ_LOCK_ASSERT(to, MA_OWNED);
9617fcf154aSJeff Roberson 
962ad1e7d28SJulian Elischer 	tdq = from;
963ae7a6b38SJeff Roberson 	cpu = TDQ_ID(to);
9649727e637SJeff Roberson 	td = tdq_steal(tdq, cpu);
9659727e637SJeff Roberson 	if (td == NULL)
96662fa74d9SJeff Roberson 		return (0);
96793ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
968ae7a6b38SJeff Roberson 	/*
969ae7a6b38SJeff Roberson 	 * Although the run queue is locked the thread may be blocked.  Lock
9707fcf154aSJeff Roberson 	 * it to clear this and acquire the run-queue lock.
971ae7a6b38SJeff Roberson 	 */
972ae7a6b38SJeff Roberson 	thread_lock(td);
9737fcf154aSJeff Roberson 	/* Drop recursive lock on from acquired via thread_lock(). */
974ae7a6b38SJeff Roberson 	TDQ_UNLOCK(from);
975ae7a6b38SJeff Roberson 	sched_rem(td);
9767b8bfa0dSJeff Roberson 	ts->ts_cpu = cpu;
977ae7a6b38SJeff Roberson 	td->td_lock = TDQ_LOCKPTR(to);
978ae7a6b38SJeff Roberson 	tdq_add(to, td, SRQ_YIELDING);
97962fa74d9SJeff Roberson 	return (1);
980356500a3SJeff Roberson }
98122bf7d9aSJeff Roberson 
982ae7a6b38SJeff Roberson /*
983ae7a6b38SJeff Roberson  * This tdq has idled.  Try to steal a thread from another cpu and switch
984ae7a6b38SJeff Roberson  * to it.
985ae7a6b38SJeff Roberson  */
98680f86c9fSJeff Roberson static int
987ad1e7d28SJulian Elischer tdq_idled(struct tdq *tdq)
98822bf7d9aSJeff Roberson {
98962fa74d9SJeff Roberson 	struct cpu_group *cg;
990ad1e7d28SJulian Elischer 	struct tdq *steal;
991c76ee827SJeff Roberson 	cpuset_t mask;
99262fa74d9SJeff Roberson 	int thresh;
993ae7a6b38SJeff Roberson 	int cpu;
99480f86c9fSJeff Roberson 
99588f530ccSJeff Roberson 	if (smp_started == 0 || steal_idle == 0)
99688f530ccSJeff Roberson 		return (1);
997c76ee827SJeff Roberson 	CPU_FILL(&mask);
998c76ee827SJeff Roberson 	CPU_CLR(PCPU_GET(cpuid), &mask);
99962fa74d9SJeff Roberson 	/* We don't want to be preempted while we're iterating. */
1000ae7a6b38SJeff Roberson 	spinlock_enter();
100162fa74d9SJeff Roberson 	for (cg = tdq->tdq_cg; cg != NULL; ) {
10027b55ab05SJeff Roberson 		if ((cg->cg_flags & CG_FLAG_THREAD) == 0)
100362fa74d9SJeff Roberson 			thresh = steal_thresh;
100462fa74d9SJeff Roberson 		else
100562fa74d9SJeff Roberson 			thresh = 1;
100662fa74d9SJeff Roberson 		cpu = sched_highest(cg, mask, thresh);
100762fa74d9SJeff Roberson 		if (cpu == -1) {
100862fa74d9SJeff Roberson 			cg = cg->cg_parent;
100980f86c9fSJeff Roberson 			continue;
10107b8bfa0dSJeff Roberson 		}
10117b8bfa0dSJeff Roberson 		steal = TDQ_CPU(cpu);
1012c76ee827SJeff Roberson 		CPU_CLR(cpu, &mask);
10137fcf154aSJeff Roberson 		tdq_lock_pair(tdq, steal);
101462fa74d9SJeff Roberson 		if (steal->tdq_load < thresh || steal->tdq_transferable == 0) {
10157fcf154aSJeff Roberson 			tdq_unlock_pair(tdq, steal);
101662fa74d9SJeff Roberson 			continue;
101762fa74d9SJeff Roberson 		}
101862fa74d9SJeff Roberson 		/*
101962fa74d9SJeff Roberson 		 * If a thread was added while interrupts were disabled don't
102062fa74d9SJeff Roberson 		 * steal one here.  If we fail to acquire one due to affinity
102162fa74d9SJeff Roberson 		 * restrictions loop again with this cpu removed from the
102262fa74d9SJeff Roberson 		 * set.
102362fa74d9SJeff Roberson 		 */
102462fa74d9SJeff Roberson 		if (tdq->tdq_load == 0 && tdq_move(steal, tdq) == 0) {
102562fa74d9SJeff Roberson 			tdq_unlock_pair(tdq, steal);
102662fa74d9SJeff Roberson 			continue;
102780f86c9fSJeff Roberson 		}
1028ae7a6b38SJeff Roberson 		spinlock_exit();
1029ae7a6b38SJeff Roberson 		TDQ_UNLOCK(steal);
10308df78c41SJeff Roberson 		mi_switch(SW_VOL | SWT_IDLE, NULL);
1031ae7a6b38SJeff Roberson 		thread_unlock(curthread);
10327b8bfa0dSJeff Roberson 
10337b8bfa0dSJeff Roberson 		return (0);
103422bf7d9aSJeff Roberson 	}
103562fa74d9SJeff Roberson 	spinlock_exit();
103662fa74d9SJeff Roberson 	return (1);
103762fa74d9SJeff Roberson }
103822bf7d9aSJeff Roberson 
1039ae7a6b38SJeff Roberson /*
1040ae7a6b38SJeff Roberson  * Notify a remote cpu of new work.  Sends an IPI if criteria are met.
1041ae7a6b38SJeff Roberson  */
104222bf7d9aSJeff Roberson static void
104327ee18adSRyan Stone tdq_notify(struct tdq *tdq, struct thread *td)
104422bf7d9aSJeff Roberson {
104502f0ff6dSJohn Baldwin 	struct thread *ctd;
104627ee18adSRyan Stone 	int pri;
10477b8bfa0dSJeff Roberson 	int cpu;
104822bf7d9aSJeff Roberson 
1049ff256d9cSJeff Roberson 	if (tdq->tdq_ipipending)
1050ff256d9cSJeff Roberson 		return;
105127ee18adSRyan Stone 	cpu = td_get_sched(td)->ts_cpu;
105227ee18adSRyan Stone 	pri = td->td_priority;
105302f0ff6dSJohn Baldwin 	ctd = pcpu_find(cpu)->pc_curthread;
105402f0ff6dSJohn Baldwin 	if (!sched_shouldpreempt(pri, ctd->td_priority, 1))
10556b2f763fSJeff Roberson 		return;
105679654969SAlexander Motin 
105779654969SAlexander Motin 	/*
1058ae9e9b4fSAlexander Motin 	 * Make sure that our caller's earlier update to tdq_load is
1059ae9e9b4fSAlexander Motin 	 * globally visible before we read tdq_cpu_idle.  Idle thread
106079654969SAlexander Motin 	 * accesses both of them without locks, and the order is important.
106179654969SAlexander Motin 	 */
1062e8677f38SKonstantin Belousov 	atomic_thread_fence_seq_cst();
106379654969SAlexander Motin 
106402f0ff6dSJohn Baldwin 	if (TD_IS_IDLETHREAD(ctd)) {
10651690c6c1SJeff Roberson 		/*
10666c47aaaeSJeff Roberson 		 * If the MD code has an idle wakeup routine try that before
10676c47aaaeSJeff Roberson 		 * falling back to IPI.
10686c47aaaeSJeff Roberson 		 */
10699f9ad565SAlexander Motin 		if (!tdq->tdq_cpu_idle || cpu_idle_wakeup(cpu))
10706c47aaaeSJeff Roberson 			return;
10711690c6c1SJeff Roberson 	}
1072ff256d9cSJeff Roberson 	tdq->tdq_ipipending = 1;
1073d9d8d144SJohn Baldwin 	ipi_cpu(cpu, IPI_PREEMPT);
107422bf7d9aSJeff Roberson }
107522bf7d9aSJeff Roberson 
1076ae7a6b38SJeff Roberson /*
1077ae7a6b38SJeff Roberson  * Steals load from a timeshare queue.  Honors the rotating queue head
1078ae7a6b38SJeff Roberson  * index.
1079ae7a6b38SJeff Roberson  */
10809727e637SJeff Roberson static struct thread *
108162fa74d9SJeff Roberson runq_steal_from(struct runq *rq, int cpu, u_char start)
1082ae7a6b38SJeff Roberson {
1083ae7a6b38SJeff Roberson 	struct rqbits *rqb;
1084ae7a6b38SJeff Roberson 	struct rqhead *rqh;
108536acfc65SAlexander Motin 	struct thread *td, *first;
1086ae7a6b38SJeff Roberson 	int bit;
1087ae7a6b38SJeff Roberson 	int i;
1088ae7a6b38SJeff Roberson 
1089ae7a6b38SJeff Roberson 	rqb = &rq->rq_status;
1090ae7a6b38SJeff Roberson 	bit = start & (RQB_BPW -1);
109136acfc65SAlexander Motin 	first = NULL;
1092ae7a6b38SJeff Roberson again:
1093ae7a6b38SJeff Roberson 	for (i = RQB_WORD(start); i < RQB_LEN; bit = 0, i++) {
1094ae7a6b38SJeff Roberson 		if (rqb->rqb_bits[i] == 0)
1095ae7a6b38SJeff Roberson 			continue;
10968bc713f6SJeff Roberson 		if (bit == 0)
10978bc713f6SJeff Roberson 			bit = RQB_FFS(rqb->rqb_bits[i]);
10988bc713f6SJeff Roberson 		for (; bit < RQB_BPW; bit++) {
10998bc713f6SJeff Roberson 			if ((rqb->rqb_bits[i] & (1ul << bit)) == 0)
1100ae7a6b38SJeff Roberson 				continue;
11018bc713f6SJeff Roberson 			rqh = &rq->rq_queues[bit + (i << RQB_L2BPW)];
11029727e637SJeff Roberson 			TAILQ_FOREACH(td, rqh, td_runq) {
11039727e637SJeff Roberson 				if (first && THREAD_CAN_MIGRATE(td) &&
11049727e637SJeff Roberson 				    THREAD_CAN_SCHED(td, cpu))
11059727e637SJeff Roberson 					return (td);
110636acfc65SAlexander Motin 				first = td;
1107ae7a6b38SJeff Roberson 			}
1108ae7a6b38SJeff Roberson 		}
11098bc713f6SJeff Roberson 	}
1110ae7a6b38SJeff Roberson 	if (start != 0) {
1111ae7a6b38SJeff Roberson 		start = 0;
1112ae7a6b38SJeff Roberson 		goto again;
1113ae7a6b38SJeff Roberson 	}
1114ae7a6b38SJeff Roberson 
111536acfc65SAlexander Motin 	if (first && THREAD_CAN_MIGRATE(first) &&
111636acfc65SAlexander Motin 	    THREAD_CAN_SCHED(first, cpu))
111736acfc65SAlexander Motin 		return (first);
1118ae7a6b38SJeff Roberson 	return (NULL);
1119ae7a6b38SJeff Roberson }
1120ae7a6b38SJeff Roberson 
1121ae7a6b38SJeff Roberson /*
1122ae7a6b38SJeff Roberson  * Steals load from a standard linear queue.
1123ae7a6b38SJeff Roberson  */
11249727e637SJeff Roberson static struct thread *
112562fa74d9SJeff Roberson runq_steal(struct runq *rq, int cpu)
112622bf7d9aSJeff Roberson {
112722bf7d9aSJeff Roberson 	struct rqhead *rqh;
112822bf7d9aSJeff Roberson 	struct rqbits *rqb;
11299727e637SJeff Roberson 	struct thread *td;
113022bf7d9aSJeff Roberson 	int word;
113122bf7d9aSJeff Roberson 	int bit;
113222bf7d9aSJeff Roberson 
113322bf7d9aSJeff Roberson 	rqb = &rq->rq_status;
113422bf7d9aSJeff Roberson 	for (word = 0; word < RQB_LEN; word++) {
113522bf7d9aSJeff Roberson 		if (rqb->rqb_bits[word] == 0)
113622bf7d9aSJeff Roberson 			continue;
113722bf7d9aSJeff Roberson 		for (bit = 0; bit < RQB_BPW; bit++) {
1138a2640c9bSPeter Wemm 			if ((rqb->rqb_bits[word] & (1ul << bit)) == 0)
113922bf7d9aSJeff Roberson 				continue;
114022bf7d9aSJeff Roberson 			rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
11419727e637SJeff Roberson 			TAILQ_FOREACH(td, rqh, td_runq)
11429727e637SJeff Roberson 				if (THREAD_CAN_MIGRATE(td) &&
11439727e637SJeff Roberson 				    THREAD_CAN_SCHED(td, cpu))
11449727e637SJeff Roberson 					return (td);
114522bf7d9aSJeff Roberson 		}
114622bf7d9aSJeff Roberson 	}
114722bf7d9aSJeff Roberson 	return (NULL);
114822bf7d9aSJeff Roberson }
114922bf7d9aSJeff Roberson 
1150ae7a6b38SJeff Roberson /*
1151ae7a6b38SJeff Roberson  * Attempt to steal a thread in priority order from a thread queue.
1152ae7a6b38SJeff Roberson  */
11539727e637SJeff Roberson static struct thread *
115462fa74d9SJeff Roberson tdq_steal(struct tdq *tdq, int cpu)
115522bf7d9aSJeff Roberson {
11569727e637SJeff Roberson 	struct thread *td;
115722bf7d9aSJeff Roberson 
1158ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
11599727e637SJeff Roberson 	if ((td = runq_steal(&tdq->tdq_realtime, cpu)) != NULL)
11609727e637SJeff Roberson 		return (td);
11619727e637SJeff Roberson 	if ((td = runq_steal_from(&tdq->tdq_timeshare,
11629727e637SJeff Roberson 	    cpu, tdq->tdq_ridx)) != NULL)
11639727e637SJeff Roberson 		return (td);
116462fa74d9SJeff Roberson 	return (runq_steal(&tdq->tdq_idle, cpu));
116522bf7d9aSJeff Roberson }
116680f86c9fSJeff Roberson 
1167ae7a6b38SJeff Roberson /*
1168ae7a6b38SJeff Roberson  * Sets the thread lock and ts_cpu to match the requested cpu.  Unlocks the
11697fcf154aSJeff Roberson  * current lock and returns with the assigned queue locked.
1170ae7a6b38SJeff Roberson  */
1171ae7a6b38SJeff Roberson static inline struct tdq *
11729727e637SJeff Roberson sched_setcpu(struct thread *td, int cpu, int flags)
117380f86c9fSJeff Roberson {
11749727e637SJeff Roberson 
1175ae7a6b38SJeff Roberson 	struct tdq *tdq;
117680f86c9fSJeff Roberson 
11779727e637SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1178ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpu);
117993ccd6bfSKonstantin Belousov 	td_get_sched(td)->ts_cpu = cpu;
11809727e637SJeff Roberson 	/*
11819727e637SJeff Roberson 	 * If the lock matches just return the queue.
11829727e637SJeff Roberson 	 */
1183ae7a6b38SJeff Roberson 	if (td->td_lock == TDQ_LOCKPTR(tdq))
1184ae7a6b38SJeff Roberson 		return (tdq);
1185ae7a6b38SJeff Roberson #ifdef notyet
118680f86c9fSJeff Roberson 	/*
1187a5423ea3SJeff Roberson 	 * If the thread isn't running its lockptr is a
1188ae7a6b38SJeff Roberson 	 * turnstile or a sleepqueue.  We can just lock_set without
1189ae7a6b38SJeff Roberson 	 * blocking.
1190670c524fSJeff Roberson 	 */
1191ae7a6b38SJeff Roberson 	if (TD_CAN_RUN(td)) {
1192ae7a6b38SJeff Roberson 		TDQ_LOCK(tdq);
1193ae7a6b38SJeff Roberson 		thread_lock_set(td, TDQ_LOCKPTR(tdq));
1194ae7a6b38SJeff Roberson 		return (tdq);
1195ae7a6b38SJeff Roberson 	}
1196ae7a6b38SJeff Roberson #endif
119780f86c9fSJeff Roberson 	/*
1198ae7a6b38SJeff Roberson 	 * The hard case, migration, we need to block the thread first to
1199ae7a6b38SJeff Roberson 	 * prevent order reversals with other cpus locks.
12007b8bfa0dSJeff Roberson 	 */
1201b0b9dee5SAttilio Rao 	spinlock_enter();
1202ae7a6b38SJeff Roberson 	thread_lock_block(td);
1203ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
1204ae7a6b38SJeff Roberson 	thread_lock_unblock(td, TDQ_LOCKPTR(tdq));
1205b0b9dee5SAttilio Rao 	spinlock_exit();
1206ae7a6b38SJeff Roberson 	return (tdq);
120780f86c9fSJeff Roberson }
12082454aaf5SJeff Roberson 
12098df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_intrbind, "Soft interrupt binding");
12108df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_idle_affinity, "Picked idle cpu based on affinity");
12118df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_affinity, "Picked cpu based on affinity");
12128df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_lowest, "Selected lowest load");
12138df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_local, "Migrated to current cpu");
12148df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_migration, "Selection may have caused migration");
12158df78c41SJeff Roberson 
1216ae7a6b38SJeff Roberson static int
12179727e637SJeff Roberson sched_pickcpu(struct thread *td, int flags)
1218ae7a6b38SJeff Roberson {
121936acfc65SAlexander Motin 	struct cpu_group *cg, *ccg;
12209727e637SJeff Roberson 	struct td_sched *ts;
1221ae7a6b38SJeff Roberson 	struct tdq *tdq;
1222c76ee827SJeff Roberson 	cpuset_t mask;
122336acfc65SAlexander Motin 	int cpu, pri, self;
12247b8bfa0dSJeff Roberson 
122562fa74d9SJeff Roberson 	self = PCPU_GET(cpuid);
122693ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
12277b8bfa0dSJeff Roberson 	if (smp_started == 0)
12287b8bfa0dSJeff Roberson 		return (self);
122928994a58SJeff Roberson 	/*
123028994a58SJeff Roberson 	 * Don't migrate a running thread from sched_switch().
123128994a58SJeff Roberson 	 */
123262fa74d9SJeff Roberson 	if ((flags & SRQ_OURSELF) || !THREAD_CAN_MIGRATE(td))
123362fa74d9SJeff Roberson 		return (ts->ts_cpu);
12347b8bfa0dSJeff Roberson 	/*
123562fa74d9SJeff Roberson 	 * Prefer to run interrupt threads on the processors that generate
123662fa74d9SJeff Roberson 	 * the interrupt.
12377b8bfa0dSJeff Roberson 	 */
123836acfc65SAlexander Motin 	pri = td->td_priority;
123962fa74d9SJeff Roberson 	if (td->td_priority <= PRI_MAX_ITHD && THREAD_CAN_SCHED(td, self) &&
12408df78c41SJeff Roberson 	    curthread->td_intr_nesting_level && ts->ts_cpu != self) {
12418df78c41SJeff Roberson 		SCHED_STAT_INC(pickcpu_intrbind);
124262fa74d9SJeff Roberson 		ts->ts_cpu = self;
124336acfc65SAlexander Motin 		if (TDQ_CPU(self)->tdq_lowpri > pri) {
12448df78c41SJeff Roberson 			SCHED_STAT_INC(pickcpu_affinity);
12457b8bfa0dSJeff Roberson 			return (ts->ts_cpu);
12467b8bfa0dSJeff Roberson 		}
12478df78c41SJeff Roberson 	}
12487b8bfa0dSJeff Roberson 	/*
124936acfc65SAlexander Motin 	 * If the thread can run on the last cpu and the affinity has not
125036acfc65SAlexander Motin 	 * expired or it is idle run it there.
12517b8bfa0dSJeff Roberson 	 */
125236acfc65SAlexander Motin 	tdq = TDQ_CPU(ts->ts_cpu);
125336acfc65SAlexander Motin 	cg = tdq->tdq_cg;
125436acfc65SAlexander Motin 	if (THREAD_CAN_SCHED(td, ts->ts_cpu) &&
125536acfc65SAlexander Motin 	    tdq->tdq_lowpri >= PRI_MIN_IDLE &&
125636acfc65SAlexander Motin 	    SCHED_AFFINITY(ts, CG_SHARE_L2)) {
125736acfc65SAlexander Motin 		if (cg->cg_flags & CG_FLAG_THREAD) {
125836acfc65SAlexander Motin 			CPUSET_FOREACH(cpu, cg->cg_mask) {
125936acfc65SAlexander Motin 				if (TDQ_CPU(cpu)->tdq_lowpri < PRI_MIN_IDLE)
126062fa74d9SJeff Roberson 					break;
126136acfc65SAlexander Motin 			}
126236acfc65SAlexander Motin 		} else
126336acfc65SAlexander Motin 			cpu = INT_MAX;
126436acfc65SAlexander Motin 		if (cpu > mp_maxid) {
126536acfc65SAlexander Motin 			SCHED_STAT_INC(pickcpu_idle_affinity);
126636acfc65SAlexander Motin 			return (ts->ts_cpu);
126736acfc65SAlexander Motin 		}
126836acfc65SAlexander Motin 	}
126936acfc65SAlexander Motin 	/*
127036acfc65SAlexander Motin 	 * Search for the last level cache CPU group in the tree.
127136acfc65SAlexander Motin 	 * Skip caches with expired affinity time and SMT groups.
127236acfc65SAlexander Motin 	 * Affinity to higher level caches will be handled less aggressively.
127336acfc65SAlexander Motin 	 */
127436acfc65SAlexander Motin 	for (ccg = NULL; cg != NULL; cg = cg->cg_parent) {
127536acfc65SAlexander Motin 		if (cg->cg_flags & CG_FLAG_THREAD)
127636acfc65SAlexander Motin 			continue;
127736acfc65SAlexander Motin 		if (!SCHED_AFFINITY(ts, cg->cg_level))
127836acfc65SAlexander Motin 			continue;
127936acfc65SAlexander Motin 		ccg = cg;
128036acfc65SAlexander Motin 	}
128136acfc65SAlexander Motin 	if (ccg != NULL)
128236acfc65SAlexander Motin 		cg = ccg;
128362fa74d9SJeff Roberson 	cpu = -1;
128436acfc65SAlexander Motin 	/* Search the group for the less loaded idle CPU we can run now. */
1285c76ee827SJeff Roberson 	mask = td->td_cpuset->cs_mask;
128636acfc65SAlexander Motin 	if (cg != NULL && cg != cpu_top &&
128736acfc65SAlexander Motin 	    CPU_CMP(&cg->cg_mask, &cpu_top->cg_mask) != 0)
128836acfc65SAlexander Motin 		cpu = sched_lowest(cg, mask, max(pri, PRI_MAX_TIMESHARE),
128936acfc65SAlexander Motin 		    INT_MAX, ts->ts_cpu);
129036acfc65SAlexander Motin 	/* Search globally for the less loaded CPU we can run now. */
129162fa74d9SJeff Roberson 	if (cpu == -1)
129236acfc65SAlexander Motin 		cpu = sched_lowest(cpu_top, mask, pri, INT_MAX, ts->ts_cpu);
129336acfc65SAlexander Motin 	/* Search globally for the less loaded CPU. */
129436acfc65SAlexander Motin 	if (cpu == -1)
129536acfc65SAlexander Motin 		cpu = sched_lowest(cpu_top, mask, -1, INT_MAX, ts->ts_cpu);
12966022f0bcSAlexander Motin 	KASSERT(cpu != -1, ("sched_pickcpu: Failed to find a cpu."));
129762fa74d9SJeff Roberson 	/*
129862fa74d9SJeff Roberson 	 * Compare the lowest loaded cpu to current cpu.
129962fa74d9SJeff Roberson 	 */
1300ff256d9cSJeff Roberson 	if (THREAD_CAN_SCHED(td, self) && TDQ_CPU(self)->tdq_lowpri > pri &&
130136acfc65SAlexander Motin 	    TDQ_CPU(cpu)->tdq_lowpri < PRI_MIN_IDLE &&
130236acfc65SAlexander Motin 	    TDQ_CPU(self)->tdq_load <= TDQ_CPU(cpu)->tdq_load + 1) {
13038df78c41SJeff Roberson 		SCHED_STAT_INC(pickcpu_local);
130462fa74d9SJeff Roberson 		cpu = self;
13058df78c41SJeff Roberson 	} else
13068df78c41SJeff Roberson 		SCHED_STAT_INC(pickcpu_lowest);
13078df78c41SJeff Roberson 	if (cpu != ts->ts_cpu)
13088df78c41SJeff Roberson 		SCHED_STAT_INC(pickcpu_migration);
1309ae7a6b38SJeff Roberson 	return (cpu);
131080f86c9fSJeff Roberson }
131162fa74d9SJeff Roberson #endif
131222bf7d9aSJeff Roberson 
131322bf7d9aSJeff Roberson /*
131422bf7d9aSJeff Roberson  * Pick the highest priority task we have and return it.
13150c0a98b2SJeff Roberson  */
13169727e637SJeff Roberson static struct thread *
1317ad1e7d28SJulian Elischer tdq_choose(struct tdq *tdq)
13185d7ef00cSJeff Roberson {
13199727e637SJeff Roberson 	struct thread *td;
13205d7ef00cSJeff Roberson 
1321ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
13229727e637SJeff Roberson 	td = runq_choose(&tdq->tdq_realtime);
13239727e637SJeff Roberson 	if (td != NULL)
13249727e637SJeff Roberson 		return (td);
13259727e637SJeff Roberson 	td = runq_choose_from(&tdq->tdq_timeshare, tdq->tdq_ridx);
13269727e637SJeff Roberson 	if (td != NULL) {
132712d56c0fSJohn Baldwin 		KASSERT(td->td_priority >= PRI_MIN_BATCH,
1328e7d50326SJeff Roberson 		    ("tdq_choose: Invalid priority on timeshare queue %d",
13299727e637SJeff Roberson 		    td->td_priority));
13309727e637SJeff Roberson 		return (td);
133115dc847eSJeff Roberson 	}
13329727e637SJeff Roberson 	td = runq_choose(&tdq->tdq_idle);
13339727e637SJeff Roberson 	if (td != NULL) {
13349727e637SJeff Roberson 		KASSERT(td->td_priority >= PRI_MIN_IDLE,
1335e7d50326SJeff Roberson 		    ("tdq_choose: Invalid priority on idle queue %d",
13369727e637SJeff Roberson 		    td->td_priority));
13379727e637SJeff Roberson 		return (td);
1338e7d50326SJeff Roberson 	}
1339e7d50326SJeff Roberson 
1340e7d50326SJeff Roberson 	return (NULL);
1341245f3abfSJeff Roberson }
13420a016a05SJeff Roberson 
1343ae7a6b38SJeff Roberson /*
1344ae7a6b38SJeff Roberson  * Initialize a thread queue.
1345ae7a6b38SJeff Roberson  */
13460a016a05SJeff Roberson static void
1347ad1e7d28SJulian Elischer tdq_setup(struct tdq *tdq)
13480a016a05SJeff Roberson {
1349ae7a6b38SJeff Roberson 
1350c47f202bSJeff Roberson 	if (bootverbose)
1351c47f202bSJeff Roberson 		printf("ULE: setup cpu %d\n", TDQ_ID(tdq));
1352e7d50326SJeff Roberson 	runq_init(&tdq->tdq_realtime);
1353e7d50326SJeff Roberson 	runq_init(&tdq->tdq_timeshare);
1354d2ad694cSJeff Roberson 	runq_init(&tdq->tdq_idle);
135562fa74d9SJeff Roberson 	snprintf(tdq->tdq_name, sizeof(tdq->tdq_name),
135662fa74d9SJeff Roberson 	    "sched lock %d", (int)TDQ_ID(tdq));
135762fa74d9SJeff Roberson 	mtx_init(&tdq->tdq_lock, tdq->tdq_name, "sched lock",
135862fa74d9SJeff Roberson 	    MTX_SPIN | MTX_RECURSE);
13598f51ad55SJeff Roberson #ifdef KTR
13608f51ad55SJeff Roberson 	snprintf(tdq->tdq_loadname, sizeof(tdq->tdq_loadname),
13618f51ad55SJeff Roberson 	    "CPU %d load", (int)TDQ_ID(tdq));
13628f51ad55SJeff Roberson #endif
13630a016a05SJeff Roberson }
13640a016a05SJeff Roberson 
1365c47f202bSJeff Roberson #ifdef SMP
1366c47f202bSJeff Roberson static void
1367c47f202bSJeff Roberson sched_setup_smp(void)
1368c47f202bSJeff Roberson {
1369c47f202bSJeff Roberson 	struct tdq *tdq;
1370c47f202bSJeff Roberson 	int i;
1371c47f202bSJeff Roberson 
137262fa74d9SJeff Roberson 	cpu_top = smp_topo();
13733aa6d94eSJohn Baldwin 	CPU_FOREACH(i) {
137462fa74d9SJeff Roberson 		tdq = TDQ_CPU(i);
1375c47f202bSJeff Roberson 		tdq_setup(tdq);
137662fa74d9SJeff Roberson 		tdq->tdq_cg = smp_topo_find(cpu_top, i);
137762fa74d9SJeff Roberson 		if (tdq->tdq_cg == NULL)
137862fa74d9SJeff Roberson 			panic("Can't find cpu group for %d\n", i);
1379c47f202bSJeff Roberson 	}
138062fa74d9SJeff Roberson 	balance_tdq = TDQ_SELF();
138162fa74d9SJeff Roberson 	sched_balance();
1382c47f202bSJeff Roberson }
1383c47f202bSJeff Roberson #endif
1384c47f202bSJeff Roberson 
1385ae7a6b38SJeff Roberson /*
1386ae7a6b38SJeff Roberson  * Setup the thread queues and initialize the topology based on MD
1387ae7a6b38SJeff Roberson  * information.
1388ae7a6b38SJeff Roberson  */
138935e6168fSJeff Roberson static void
139035e6168fSJeff Roberson sched_setup(void *dummy)
139135e6168fSJeff Roberson {
1392ae7a6b38SJeff Roberson 	struct tdq *tdq;
1393c47f202bSJeff Roberson 
1394c47f202bSJeff Roberson 	tdq = TDQ_SELF();
13950ec896fdSJeff Roberson #ifdef SMP
1396c47f202bSJeff Roberson 	sched_setup_smp();
1397749d01b0SJeff Roberson #else
1398c47f202bSJeff Roberson 	tdq_setup(tdq);
1399356500a3SJeff Roberson #endif
1400ae7a6b38SJeff Roberson 
1401ae7a6b38SJeff Roberson 	/* Add thread0's load since it's running. */
1402ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
1403c47f202bSJeff Roberson 	thread0.td_lock = TDQ_LOCKPTR(TDQ_SELF());
14049727e637SJeff Roberson 	tdq_load_add(tdq, &thread0);
140562fa74d9SJeff Roberson 	tdq->tdq_lowpri = thread0.td_priority;
1406ae7a6b38SJeff Roberson 	TDQ_UNLOCK(tdq);
140735e6168fSJeff Roberson }
140835e6168fSJeff Roberson 
1409ae7a6b38SJeff Roberson /*
1410579895dfSAlexander Motin  * This routine determines time constants after stathz and hz are setup.
1411ae7a6b38SJeff Roberson  */
1412a1d4fe69SDavid Xu /* ARGSUSED */
1413a1d4fe69SDavid Xu static void
1414a1d4fe69SDavid Xu sched_initticks(void *dummy)
1415a1d4fe69SDavid Xu {
1416ae7a6b38SJeff Roberson 	int incr;
1417ae7a6b38SJeff Roberson 
1418a1d4fe69SDavid Xu 	realstathz = stathz ? stathz : hz;
14195e5c3873SJeff Roberson 	sched_slice = realstathz / SCHED_SLICE_DEFAULT_DIVISOR;
14205e5c3873SJeff Roberson 	sched_slice_min = sched_slice / SCHED_SLICE_MIN_DIVISOR;
142137f4e025SAlexander Motin 	hogticks = imax(1, (2 * hz * sched_slice + realstathz / 2) /
142237f4e025SAlexander Motin 	    realstathz);
1423a1d4fe69SDavid Xu 
1424a1d4fe69SDavid Xu 	/*
1425e7d50326SJeff Roberson 	 * tickincr is shifted out by 10 to avoid rounding errors due to
14263f872f85SJeff Roberson 	 * hz not being evenly divisible by stathz on all platforms.
1427e7d50326SJeff Roberson 	 */
1428ae7a6b38SJeff Roberson 	incr = (hz << SCHED_TICK_SHIFT) / realstathz;
1429e7d50326SJeff Roberson 	/*
1430e7d50326SJeff Roberson 	 * This does not work for values of stathz that are more than
1431e7d50326SJeff Roberson 	 * 1 << SCHED_TICK_SHIFT * hz.  In practice this does not happen.
1432a1d4fe69SDavid Xu 	 */
1433ae7a6b38SJeff Roberson 	if (incr == 0)
1434ae7a6b38SJeff Roberson 		incr = 1;
1435ae7a6b38SJeff Roberson 	tickincr = incr;
14367b8bfa0dSJeff Roberson #ifdef SMP
14379862717aSJeff Roberson 	/*
14387fcf154aSJeff Roberson 	 * Set the default balance interval now that we know
14397fcf154aSJeff Roberson 	 * what realstathz is.
14407fcf154aSJeff Roberson 	 */
14417fcf154aSJeff Roberson 	balance_interval = realstathz;
14427b8bfa0dSJeff Roberson 	affinity = SCHED_AFFINITY_DEFAULT;
14437b8bfa0dSJeff Roberson #endif
1444b3f40a41SAlexander Motin 	if (sched_idlespinthresh < 0)
14452c27cb3aSAlexander Motin 		sched_idlespinthresh = 2 * max(10000, 6 * hz) / realstathz;
1446a1d4fe69SDavid Xu }
1447a1d4fe69SDavid Xu 
1448a1d4fe69SDavid Xu 
144935e6168fSJeff Roberson /*
1450ae7a6b38SJeff Roberson  * This is the core of the interactivity algorithm.  Determines a score based
1451ae7a6b38SJeff Roberson  * on past behavior.  It is the ratio of sleep time to run time scaled to
1452ae7a6b38SJeff Roberson  * a [0, 100] integer.  This is the voluntary sleep time of a process, which
1453ae7a6b38SJeff Roberson  * differs from the cpu usage because it does not account for time spent
1454ae7a6b38SJeff Roberson  * waiting on a run-queue.  Would be prettier if we had floating point.
145557031f79SGeorge V. Neville-Neil  *
145657031f79SGeorge V. Neville-Neil  * When a thread's sleep time is greater than its run time the
145757031f79SGeorge V. Neville-Neil  * calculation is:
145857031f79SGeorge V. Neville-Neil  *
145957031f79SGeorge V. Neville-Neil  *                           scaling factor
146057031f79SGeorge V. Neville-Neil  * interactivity score =  ---------------------
146157031f79SGeorge V. Neville-Neil  *                        sleep time / run time
146257031f79SGeorge V. Neville-Neil  *
146357031f79SGeorge V. Neville-Neil  *
146457031f79SGeorge V. Neville-Neil  * When a thread's run time is greater than its sleep time the
146557031f79SGeorge V. Neville-Neil  * calculation is:
146657031f79SGeorge V. Neville-Neil  *
146757031f79SGeorge V. Neville-Neil  *                           scaling factor
146857031f79SGeorge V. Neville-Neil  * interactivity score =  ---------------------    + scaling factor
146957031f79SGeorge V. Neville-Neil  *                        run time / sleep time
1470ae7a6b38SJeff Roberson  */
1471ae7a6b38SJeff Roberson static int
1472ae7a6b38SJeff Roberson sched_interact_score(struct thread *td)
1473ae7a6b38SJeff Roberson {
1474ae7a6b38SJeff Roberson 	struct td_sched *ts;
1475ae7a6b38SJeff Roberson 	int div;
1476ae7a6b38SJeff Roberson 
147793ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
1478ae7a6b38SJeff Roberson 	/*
1479ae7a6b38SJeff Roberson 	 * The score is only needed if this is likely to be an interactive
1480ae7a6b38SJeff Roberson 	 * task.  Don't go through the expense of computing it if there's
1481ae7a6b38SJeff Roberson 	 * no chance.
1482ae7a6b38SJeff Roberson 	 */
1483ae7a6b38SJeff Roberson 	if (sched_interact <= SCHED_INTERACT_HALF &&
1484ae7a6b38SJeff Roberson 		ts->ts_runtime >= ts->ts_slptime)
1485ae7a6b38SJeff Roberson 			return (SCHED_INTERACT_HALF);
1486ae7a6b38SJeff Roberson 
1487ae7a6b38SJeff Roberson 	if (ts->ts_runtime > ts->ts_slptime) {
1488ae7a6b38SJeff Roberson 		div = max(1, ts->ts_runtime / SCHED_INTERACT_HALF);
1489ae7a6b38SJeff Roberson 		return (SCHED_INTERACT_HALF +
1490ae7a6b38SJeff Roberson 		    (SCHED_INTERACT_HALF - (ts->ts_slptime / div)));
1491ae7a6b38SJeff Roberson 	}
1492ae7a6b38SJeff Roberson 	if (ts->ts_slptime > ts->ts_runtime) {
1493ae7a6b38SJeff Roberson 		div = max(1, ts->ts_slptime / SCHED_INTERACT_HALF);
1494ae7a6b38SJeff Roberson 		return (ts->ts_runtime / div);
1495ae7a6b38SJeff Roberson 	}
1496ae7a6b38SJeff Roberson 	/* runtime == slptime */
1497ae7a6b38SJeff Roberson 	if (ts->ts_runtime)
1498ae7a6b38SJeff Roberson 		return (SCHED_INTERACT_HALF);
1499ae7a6b38SJeff Roberson 
1500ae7a6b38SJeff Roberson 	/*
1501ae7a6b38SJeff Roberson 	 * This can happen if slptime and runtime are 0.
1502ae7a6b38SJeff Roberson 	 */
1503ae7a6b38SJeff Roberson 	return (0);
1504ae7a6b38SJeff Roberson 
1505ae7a6b38SJeff Roberson }
1506ae7a6b38SJeff Roberson 
1507ae7a6b38SJeff Roberson /*
150835e6168fSJeff Roberson  * Scale the scheduling priority according to the "interactivity" of this
150935e6168fSJeff Roberson  * process.
151035e6168fSJeff Roberson  */
151115dc847eSJeff Roberson static void
15128460a577SJohn Birrell sched_priority(struct thread *td)
151335e6168fSJeff Roberson {
1514e7d50326SJeff Roberson 	int score;
151535e6168fSJeff Roberson 	int pri;
151635e6168fSJeff Roberson 
1517c9a8cba4SJohn Baldwin 	if (PRI_BASE(td->td_pri_class) != PRI_TIMESHARE)
151815dc847eSJeff Roberson 		return;
1519e7d50326SJeff Roberson 	/*
1520e7d50326SJeff Roberson 	 * If the score is interactive we place the thread in the realtime
1521e7d50326SJeff Roberson 	 * queue with a priority that is less than kernel and interrupt
1522e7d50326SJeff Roberson 	 * priorities.  These threads are not subject to nice restrictions.
1523e7d50326SJeff Roberson 	 *
1524ae7a6b38SJeff Roberson 	 * Scores greater than this are placed on the normal timeshare queue
1525e7d50326SJeff Roberson 	 * where the priority is partially decided by the most recent cpu
1526e7d50326SJeff Roberson 	 * utilization and the rest is decided by nice value.
1527a5423ea3SJeff Roberson 	 *
1528a5423ea3SJeff Roberson 	 * The nice value of the process has a linear effect on the calculated
1529a5423ea3SJeff Roberson 	 * score.  Negative nice values make it easier for a thread to be
1530a5423ea3SJeff Roberson 	 * considered interactive.
1531e7d50326SJeff Roberson 	 */
1532a0f15352SJohn Baldwin 	score = imax(0, sched_interact_score(td) + td->td_proc->p_nice);
1533e7d50326SJeff Roberson 	if (score < sched_interact) {
153412d56c0fSJohn Baldwin 		pri = PRI_MIN_INTERACT;
153512d56c0fSJohn Baldwin 		pri += ((PRI_MAX_INTERACT - PRI_MIN_INTERACT + 1) /
153678920008SJohn Baldwin 		    sched_interact) * score;
153712d56c0fSJohn Baldwin 		KASSERT(pri >= PRI_MIN_INTERACT && pri <= PRI_MAX_INTERACT,
15389a93305aSJeff Roberson 		    ("sched_priority: invalid interactive priority %d score %d",
15399a93305aSJeff Roberson 		    pri, score));
1540e7d50326SJeff Roberson 	} else {
1541e7d50326SJeff Roberson 		pri = SCHED_PRI_MIN;
154293ccd6bfSKonstantin Belousov 		if (td_get_sched(td)->ts_ticks)
154393ccd6bfSKonstantin Belousov 			pri += min(SCHED_PRI_TICKS(td_get_sched(td)),
15445457fa23SJohn Baldwin 			    SCHED_PRI_RANGE - 1);
1545e7d50326SJeff Roberson 		pri += SCHED_PRI_NICE(td->td_proc->p_nice);
154612d56c0fSJohn Baldwin 		KASSERT(pri >= PRI_MIN_BATCH && pri <= PRI_MAX_BATCH,
1547ae7a6b38SJeff Roberson 		    ("sched_priority: invalid priority %d: nice %d, "
1548ae7a6b38SJeff Roberson 		    "ticks %d ftick %d ltick %d tick pri %d",
154993ccd6bfSKonstantin Belousov 		    pri, td->td_proc->p_nice, td_get_sched(td)->ts_ticks,
155093ccd6bfSKonstantin Belousov 		    td_get_sched(td)->ts_ftick, td_get_sched(td)->ts_ltick,
155193ccd6bfSKonstantin Belousov 		    SCHED_PRI_TICKS(td_get_sched(td))));
1552e7d50326SJeff Roberson 	}
15538460a577SJohn Birrell 	sched_user_prio(td, pri);
155435e6168fSJeff Roberson 
155515dc847eSJeff Roberson 	return;
155635e6168fSJeff Roberson }
155735e6168fSJeff Roberson 
155835e6168fSJeff Roberson /*
1559d322132cSJeff Roberson  * This routine enforces a maximum limit on the amount of scheduling history
1560ae7a6b38SJeff Roberson  * kept.  It is called after either the slptime or runtime is adjusted.  This
1561ae7a6b38SJeff Roberson  * function is ugly due to integer math.
1562d322132cSJeff Roberson  */
15634b60e324SJeff Roberson static void
15648460a577SJohn Birrell sched_interact_update(struct thread *td)
15654b60e324SJeff Roberson {
1566155b6ca1SJeff Roberson 	struct td_sched *ts;
15679a93305aSJeff Roberson 	u_int sum;
15683f741ca1SJeff Roberson 
156993ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
1570ae7a6b38SJeff Roberson 	sum = ts->ts_runtime + ts->ts_slptime;
1571d322132cSJeff Roberson 	if (sum < SCHED_SLP_RUN_MAX)
1572d322132cSJeff Roberson 		return;
1573d322132cSJeff Roberson 	/*
1574155b6ca1SJeff Roberson 	 * This only happens from two places:
1575155b6ca1SJeff Roberson 	 * 1) We have added an unusual amount of run time from fork_exit.
1576155b6ca1SJeff Roberson 	 * 2) We have added an unusual amount of sleep time from sched_sleep().
1577155b6ca1SJeff Roberson 	 */
1578155b6ca1SJeff Roberson 	if (sum > SCHED_SLP_RUN_MAX * 2) {
1579ae7a6b38SJeff Roberson 		if (ts->ts_runtime > ts->ts_slptime) {
1580ae7a6b38SJeff Roberson 			ts->ts_runtime = SCHED_SLP_RUN_MAX;
1581ae7a6b38SJeff Roberson 			ts->ts_slptime = 1;
1582155b6ca1SJeff Roberson 		} else {
1583ae7a6b38SJeff Roberson 			ts->ts_slptime = SCHED_SLP_RUN_MAX;
1584ae7a6b38SJeff Roberson 			ts->ts_runtime = 1;
1585155b6ca1SJeff Roberson 		}
1586155b6ca1SJeff Roberson 		return;
1587155b6ca1SJeff Roberson 	}
1588155b6ca1SJeff Roberson 	/*
1589d322132cSJeff Roberson 	 * If we have exceeded by more than 1/5th then the algorithm below
1590d322132cSJeff Roberson 	 * will not bring us back into range.  Dividing by two here forces
15912454aaf5SJeff Roberson 	 * us into the range of [4/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX]
1592d322132cSJeff Roberson 	 */
159337a35e4aSJeff Roberson 	if (sum > (SCHED_SLP_RUN_MAX / 5) * 6) {
1594ae7a6b38SJeff Roberson 		ts->ts_runtime /= 2;
1595ae7a6b38SJeff Roberson 		ts->ts_slptime /= 2;
1596d322132cSJeff Roberson 		return;
1597d322132cSJeff Roberson 	}
1598ae7a6b38SJeff Roberson 	ts->ts_runtime = (ts->ts_runtime / 5) * 4;
1599ae7a6b38SJeff Roberson 	ts->ts_slptime = (ts->ts_slptime / 5) * 4;
1600d322132cSJeff Roberson }
1601d322132cSJeff Roberson 
1602ae7a6b38SJeff Roberson /*
1603ae7a6b38SJeff Roberson  * Scale back the interactivity history when a child thread is created.  The
1604ae7a6b38SJeff Roberson  * history is inherited from the parent but the thread may behave totally
1605ae7a6b38SJeff Roberson  * differently.  For example, a shell spawning a compiler process.  We want
1606ae7a6b38SJeff Roberson  * to learn that the compiler is behaving badly very quickly.
1607ae7a6b38SJeff Roberson  */
1608d322132cSJeff Roberson static void
16098460a577SJohn Birrell sched_interact_fork(struct thread *td)
1610d322132cSJeff Roberson {
161193ccd6bfSKonstantin Belousov 	struct td_sched *ts;
1612d322132cSJeff Roberson 	int ratio;
1613d322132cSJeff Roberson 	int sum;
1614d322132cSJeff Roberson 
161593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
161693ccd6bfSKonstantin Belousov 	sum = ts->ts_runtime + ts->ts_slptime;
1617d322132cSJeff Roberson 	if (sum > SCHED_SLP_RUN_FORK) {
1618d322132cSJeff Roberson 		ratio = sum / SCHED_SLP_RUN_FORK;
161993ccd6bfSKonstantin Belousov 		ts->ts_runtime /= ratio;
162093ccd6bfSKonstantin Belousov 		ts->ts_slptime /= ratio;
16214b60e324SJeff Roberson 	}
16224b60e324SJeff Roberson }
16234b60e324SJeff Roberson 
162415dc847eSJeff Roberson /*
1625ae7a6b38SJeff Roberson  * Called from proc0_init() to setup the scheduler fields.
1626ed062c8dSJulian Elischer  */
1627ed062c8dSJulian Elischer void
1628ed062c8dSJulian Elischer schedinit(void)
1629ed062c8dSJulian Elischer {
163093ccd6bfSKonstantin Belousov 	struct td_sched *ts0;
1631e7d50326SJeff Roberson 
1632ed062c8dSJulian Elischer 	/*
163393ccd6bfSKonstantin Belousov 	 * Set up the scheduler specific parts of thread0.
1634ed062c8dSJulian Elischer 	 */
163593ccd6bfSKonstantin Belousov 	ts0 = td_get_sched(&thread0);
163693ccd6bfSKonstantin Belousov 	ts0->ts_ltick = ticks;
163793ccd6bfSKonstantin Belousov 	ts0->ts_ftick = ticks;
163893ccd6bfSKonstantin Belousov 	ts0->ts_slice = 0;
1639ed062c8dSJulian Elischer }
1640ed062c8dSJulian Elischer 
1641ed062c8dSJulian Elischer /*
164215dc847eSJeff Roberson  * This is only somewhat accurate since given many processes of the same
164315dc847eSJeff Roberson  * priority they will switch when their slices run out, which will be
1644e7d50326SJeff Roberson  * at most sched_slice stathz ticks.
164515dc847eSJeff Roberson  */
164635e6168fSJeff Roberson int
164735e6168fSJeff Roberson sched_rr_interval(void)
164835e6168fSJeff Roberson {
1649e7d50326SJeff Roberson 
1650579895dfSAlexander Motin 	/* Convert sched_slice from stathz to hz. */
165137f4e025SAlexander Motin 	return (imax(1, (sched_slice * hz + realstathz / 2) / realstathz));
165235e6168fSJeff Roberson }
165335e6168fSJeff Roberson 
1654ae7a6b38SJeff Roberson /*
1655ae7a6b38SJeff Roberson  * Update the percent cpu tracking information when it is requested or
1656ae7a6b38SJeff Roberson  * the total history exceeds the maximum.  We keep a sliding history of
1657ae7a6b38SJeff Roberson  * tick counts that slowly decays.  This is less precise than the 4BSD
1658ae7a6b38SJeff Roberson  * mechanism since it happens with less regular and frequent events.
1659ae7a6b38SJeff Roberson  */
166022bf7d9aSJeff Roberson static void
16617295465eSAlexander Motin sched_pctcpu_update(struct td_sched *ts, int run)
166235e6168fSJeff Roberson {
16637295465eSAlexander Motin 	int t = ticks;
1664e7d50326SJeff Roberson 
1665*78133024SMark Johnston 	/*
1666*78133024SMark Johnston 	 * The signed difference may be negative if the thread hasn't run for
1667*78133024SMark Johnston 	 * over half of the ticks rollover period.
1668*78133024SMark Johnston 	 */
1669*78133024SMark Johnston 	if ((u_int)(t - ts->ts_ltick) >= SCHED_TICK_TARG) {
1670ad1e7d28SJulian Elischer 		ts->ts_ticks = 0;
16717295465eSAlexander Motin 		ts->ts_ftick = t - SCHED_TICK_TARG;
16727295465eSAlexander Motin 	} else if (t - ts->ts_ftick >= SCHED_TICK_MAX) {
16737295465eSAlexander Motin 		ts->ts_ticks = (ts->ts_ticks / (ts->ts_ltick - ts->ts_ftick)) *
16747295465eSAlexander Motin 		    (ts->ts_ltick - (t - SCHED_TICK_TARG));
16757295465eSAlexander Motin 		ts->ts_ftick = t - SCHED_TICK_TARG;
16767295465eSAlexander Motin 	}
16777295465eSAlexander Motin 	if (run)
16787295465eSAlexander Motin 		ts->ts_ticks += (t - ts->ts_ltick) << SCHED_TICK_SHIFT;
16797295465eSAlexander Motin 	ts->ts_ltick = t;
168035e6168fSJeff Roberson }
168135e6168fSJeff Roberson 
1682ae7a6b38SJeff Roberson /*
1683ae7a6b38SJeff Roberson  * Adjust the priority of a thread.  Move it to the appropriate run-queue
1684ae7a6b38SJeff Roberson  * if necessary.  This is the back-end for several priority related
1685ae7a6b38SJeff Roberson  * functions.
1686ae7a6b38SJeff Roberson  */
1687e7d50326SJeff Roberson static void
1688f5c157d9SJohn Baldwin sched_thread_priority(struct thread *td, u_char prio)
168935e6168fSJeff Roberson {
1690ad1e7d28SJulian Elischer 	struct td_sched *ts;
169173daf66fSJeff Roberson 	struct tdq *tdq;
169273daf66fSJeff Roberson 	int oldpri;
169335e6168fSJeff Roberson 
16948f51ad55SJeff Roberson 	KTR_POINT3(KTR_SCHED, "thread", sched_tdname(td), "prio",
16958f51ad55SJeff Roberson 	    "prio:%d", td->td_priority, "new prio:%d", prio,
16968f51ad55SJeff Roberson 	    KTR_ATTR_LINKED, sched_tdname(curthread));
1697d9fae5abSAndriy Gapon 	SDT_PROBE3(sched, , , change__pri, td, td->td_proc, prio);
1698e87fc7cfSAndriy Gapon 	if (td != curthread && prio < td->td_priority) {
16998f51ad55SJeff Roberson 		KTR_POINT3(KTR_SCHED, "thread", sched_tdname(curthread),
17008f51ad55SJeff Roberson 		    "lend prio", "prio:%d", td->td_priority, "new prio:%d",
17018f51ad55SJeff Roberson 		    prio, KTR_ATTR_LINKED, sched_tdname(td));
1702d9fae5abSAndriy Gapon 		SDT_PROBE4(sched, , , lend__pri, td, td->td_proc, prio,
1703b3e9e682SRyan Stone 		    curthread);
17048f51ad55SJeff Roberson 	}
170593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
17067b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1707f5c157d9SJohn Baldwin 	if (td->td_priority == prio)
1708f5c157d9SJohn Baldwin 		return;
17093f741ca1SJeff Roberson 	/*
17103f741ca1SJeff Roberson 	 * If the priority has been elevated due to priority
17113f741ca1SJeff Roberson 	 * propagation, we may have to move ourselves to a new
1712e7d50326SJeff Roberson 	 * queue.  This could be optimized to not re-add in some
1713e7d50326SJeff Roberson 	 * cases.
1714f2b74cbfSJeff Roberson 	 */
17156d55b3ecSJeff Roberson 	if (TD_ON_RUNQ(td) && prio < td->td_priority) {
1716e7d50326SJeff Roberson 		sched_rem(td);
1717e7d50326SJeff Roberson 		td->td_priority = prio;
1718ae7a6b38SJeff Roberson 		sched_add(td, SRQ_BORROWING);
171973daf66fSJeff Roberson 		return;
172073daf66fSJeff Roberson 	}
17216d55b3ecSJeff Roberson 	/*
17226d55b3ecSJeff Roberson 	 * If the thread is currently running we may have to adjust the lowpri
17236d55b3ecSJeff Roberson 	 * information so other cpus are aware of our current priority.
17246d55b3ecSJeff Roberson 	 */
17256d55b3ecSJeff Roberson 	if (TD_IS_RUNNING(td)) {
1726ae7a6b38SJeff Roberson 		tdq = TDQ_CPU(ts->ts_cpu);
172762fa74d9SJeff Roberson 		oldpri = td->td_priority;
17283f741ca1SJeff Roberson 		td->td_priority = prio;
172962fa74d9SJeff Roberson 		if (prio < tdq->tdq_lowpri)
173062fa74d9SJeff Roberson 			tdq->tdq_lowpri = prio;
173162fa74d9SJeff Roberson 		else if (tdq->tdq_lowpri == oldpri)
173262fa74d9SJeff Roberson 			tdq_setlowpri(tdq, td);
17336d55b3ecSJeff Roberson 		return;
173473daf66fSJeff Roberson 	}
17356d55b3ecSJeff Roberson 	td->td_priority = prio;
1736ae7a6b38SJeff Roberson }
173735e6168fSJeff Roberson 
1738f5c157d9SJohn Baldwin /*
1739f5c157d9SJohn Baldwin  * Update a thread's priority when it is lent another thread's
1740f5c157d9SJohn Baldwin  * priority.
1741f5c157d9SJohn Baldwin  */
1742f5c157d9SJohn Baldwin void
1743f5c157d9SJohn Baldwin sched_lend_prio(struct thread *td, u_char prio)
1744f5c157d9SJohn Baldwin {
1745f5c157d9SJohn Baldwin 
1746f5c157d9SJohn Baldwin 	td->td_flags |= TDF_BORROWING;
1747f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1748f5c157d9SJohn Baldwin }
1749f5c157d9SJohn Baldwin 
1750f5c157d9SJohn Baldwin /*
1751f5c157d9SJohn Baldwin  * Restore a thread's priority when priority propagation is
1752f5c157d9SJohn Baldwin  * over.  The prio argument is the minimum priority the thread
1753f5c157d9SJohn Baldwin  * needs to have to satisfy other possible priority lending
1754f5c157d9SJohn Baldwin  * requests.  If the thread's regular priority is less
1755f5c157d9SJohn Baldwin  * important than prio, the thread will keep a priority boost
1756f5c157d9SJohn Baldwin  * of prio.
1757f5c157d9SJohn Baldwin  */
1758f5c157d9SJohn Baldwin void
1759f5c157d9SJohn Baldwin sched_unlend_prio(struct thread *td, u_char prio)
1760f5c157d9SJohn Baldwin {
1761f5c157d9SJohn Baldwin 	u_char base_pri;
1762f5c157d9SJohn Baldwin 
1763f5c157d9SJohn Baldwin 	if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
1764f5c157d9SJohn Baldwin 	    td->td_base_pri <= PRI_MAX_TIMESHARE)
17658460a577SJohn Birrell 		base_pri = td->td_user_pri;
1766f5c157d9SJohn Baldwin 	else
1767f5c157d9SJohn Baldwin 		base_pri = td->td_base_pri;
1768f5c157d9SJohn Baldwin 	if (prio >= base_pri) {
1769f5c157d9SJohn Baldwin 		td->td_flags &= ~TDF_BORROWING;
1770f5c157d9SJohn Baldwin 		sched_thread_priority(td, base_pri);
1771f5c157d9SJohn Baldwin 	} else
1772f5c157d9SJohn Baldwin 		sched_lend_prio(td, prio);
1773f5c157d9SJohn Baldwin }
1774f5c157d9SJohn Baldwin 
1775ae7a6b38SJeff Roberson /*
1776ae7a6b38SJeff Roberson  * Standard entry for setting the priority to an absolute value.
1777ae7a6b38SJeff Roberson  */
1778f5c157d9SJohn Baldwin void
1779f5c157d9SJohn Baldwin sched_prio(struct thread *td, u_char prio)
1780f5c157d9SJohn Baldwin {
1781f5c157d9SJohn Baldwin 	u_char oldprio;
1782f5c157d9SJohn Baldwin 
1783f5c157d9SJohn Baldwin 	/* First, update the base priority. */
1784f5c157d9SJohn Baldwin 	td->td_base_pri = prio;
1785f5c157d9SJohn Baldwin 
1786f5c157d9SJohn Baldwin 	/*
178750aaa791SJohn Baldwin 	 * If the thread is borrowing another thread's priority, don't
1788f5c157d9SJohn Baldwin 	 * ever lower the priority.
1789f5c157d9SJohn Baldwin 	 */
1790f5c157d9SJohn Baldwin 	if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
1791f5c157d9SJohn Baldwin 		return;
1792f5c157d9SJohn Baldwin 
1793f5c157d9SJohn Baldwin 	/* Change the real priority. */
1794f5c157d9SJohn Baldwin 	oldprio = td->td_priority;
1795f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1796f5c157d9SJohn Baldwin 
1797f5c157d9SJohn Baldwin 	/*
1798f5c157d9SJohn Baldwin 	 * If the thread is on a turnstile, then let the turnstile update
1799f5c157d9SJohn Baldwin 	 * its state.
1800f5c157d9SJohn Baldwin 	 */
1801f5c157d9SJohn Baldwin 	if (TD_ON_LOCK(td) && oldprio != prio)
1802f5c157d9SJohn Baldwin 		turnstile_adjust(td, oldprio);
1803f5c157d9SJohn Baldwin }
1804f5c157d9SJohn Baldwin 
1805ae7a6b38SJeff Roberson /*
1806ae7a6b38SJeff Roberson  * Set the base user priority, does not effect current running priority.
1807ae7a6b38SJeff Roberson  */
180835e6168fSJeff Roberson void
18098460a577SJohn Birrell sched_user_prio(struct thread *td, u_char prio)
18103db720fdSDavid Xu {
18113db720fdSDavid Xu 
18128460a577SJohn Birrell 	td->td_base_user_pri = prio;
1813acbe332aSDavid Xu 	if (td->td_lend_user_pri <= prio)
1814fc6c30f6SJulian Elischer 		return;
18158460a577SJohn Birrell 	td->td_user_pri = prio;
18163db720fdSDavid Xu }
18173db720fdSDavid Xu 
18183db720fdSDavid Xu void
18193db720fdSDavid Xu sched_lend_user_prio(struct thread *td, u_char prio)
18203db720fdSDavid Xu {
18213db720fdSDavid Xu 
1822435806d3SDavid Xu 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1823acbe332aSDavid Xu 	td->td_lend_user_pri = prio;
1824c8e368a9SDavid Xu 	td->td_user_pri = min(prio, td->td_base_user_pri);
1825c8e368a9SDavid Xu 	if (td->td_priority > td->td_user_pri)
1826c8e368a9SDavid Xu 		sched_prio(td, td->td_user_pri);
1827c8e368a9SDavid Xu 	else if (td->td_priority != td->td_user_pri)
1828c8e368a9SDavid Xu 		td->td_flags |= TDF_NEEDRESCHED;
1829435806d3SDavid Xu }
18303db720fdSDavid Xu 
1831ae7a6b38SJeff Roberson /*
1832c47f202bSJeff Roberson  * Handle migration from sched_switch().  This happens only for
1833c47f202bSJeff Roberson  * cpu binding.
1834c47f202bSJeff Roberson  */
1835c47f202bSJeff Roberson static struct mtx *
1836c47f202bSJeff Roberson sched_switch_migrate(struct tdq *tdq, struct thread *td, int flags)
1837c47f202bSJeff Roberson {
1838c47f202bSJeff Roberson 	struct tdq *tdn;
1839c47f202bSJeff Roberson 
184093ccd6bfSKonstantin Belousov 	tdn = TDQ_CPU(td_get_sched(td)->ts_cpu);
1841c47f202bSJeff Roberson #ifdef SMP
18429727e637SJeff Roberson 	tdq_load_rem(tdq, td);
1843c47f202bSJeff Roberson 	/*
1844c47f202bSJeff Roberson 	 * Do the lock dance required to avoid LOR.  We grab an extra
1845c47f202bSJeff Roberson 	 * spinlock nesting to prevent preemption while we're
1846c47f202bSJeff Roberson 	 * not holding either run-queue lock.
1847c47f202bSJeff Roberson 	 */
1848c47f202bSJeff Roberson 	spinlock_enter();
1849b0b9dee5SAttilio Rao 	thread_lock_block(td);	/* This releases the lock on tdq. */
1850435068aaSAttilio Rao 
1851435068aaSAttilio Rao 	/*
1852435068aaSAttilio Rao 	 * Acquire both run-queue locks before placing the thread on the new
1853435068aaSAttilio Rao 	 * run-queue to avoid deadlocks created by placing a thread with a
1854435068aaSAttilio Rao 	 * blocked lock on the run-queue of a remote processor.  The deadlock
1855435068aaSAttilio Rao 	 * occurs when a third processor attempts to lock the two queues in
1856435068aaSAttilio Rao 	 * question while the target processor is spinning with its own
1857435068aaSAttilio Rao 	 * run-queue lock held while waiting for the blocked lock to clear.
1858435068aaSAttilio Rao 	 */
1859435068aaSAttilio Rao 	tdq_lock_pair(tdn, tdq);
1860c47f202bSJeff Roberson 	tdq_add(tdn, td, flags);
186127ee18adSRyan Stone 	tdq_notify(tdn, td);
1862c47f202bSJeff Roberson 	TDQ_UNLOCK(tdn);
1863c47f202bSJeff Roberson 	spinlock_exit();
1864c47f202bSJeff Roberson #endif
1865c47f202bSJeff Roberson 	return (TDQ_LOCKPTR(tdn));
1866c47f202bSJeff Roberson }
1867c47f202bSJeff Roberson 
1868c47f202bSJeff Roberson /*
1869b0b9dee5SAttilio Rao  * Variadic version of thread_lock_unblock() that does not assume td_lock
1870b0b9dee5SAttilio Rao  * is blocked.
1871ae7a6b38SJeff Roberson  */
1872ae7a6b38SJeff Roberson static inline void
1873ae7a6b38SJeff Roberson thread_unblock_switch(struct thread *td, struct mtx *mtx)
1874ae7a6b38SJeff Roberson {
1875ae7a6b38SJeff Roberson 	atomic_store_rel_ptr((volatile uintptr_t *)&td->td_lock,
1876ae7a6b38SJeff Roberson 	    (uintptr_t)mtx);
1877ae7a6b38SJeff Roberson }
1878ae7a6b38SJeff Roberson 
1879ae7a6b38SJeff Roberson /*
1880ae7a6b38SJeff Roberson  * Switch threads.  This function has to handle threads coming in while
1881ae7a6b38SJeff Roberson  * blocked for some reason, running, or idle.  It also must deal with
1882ae7a6b38SJeff Roberson  * migrating a thread from one queue to another as running threads may
1883ae7a6b38SJeff Roberson  * be assigned elsewhere via binding.
1884ae7a6b38SJeff Roberson  */
18853db720fdSDavid Xu void
18863389af30SJulian Elischer sched_switch(struct thread *td, struct thread *newtd, int flags)
188735e6168fSJeff Roberson {
1888c02bbb43SJeff Roberson 	struct tdq *tdq;
1889ad1e7d28SJulian Elischer 	struct td_sched *ts;
1890ae7a6b38SJeff Roberson 	struct mtx *mtx;
1891c47f202bSJeff Roberson 	int srqflag;
18923d7f4117SAlexander Motin 	int cpuid, preempted;
189335e6168fSJeff Roberson 
18947b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
18956d55b3ecSJeff Roberson 	KASSERT(newtd == NULL, ("sched_switch: Unsupported newtd argument"));
189635e6168fSJeff Roberson 
1897ae7a6b38SJeff Roberson 	cpuid = PCPU_GET(cpuid);
1898ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpuid);
189993ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
1900c47f202bSJeff Roberson 	mtx = td->td_lock;
19017295465eSAlexander Motin 	sched_pctcpu_update(ts, 1);
1902ae7a6b38SJeff Roberson 	ts->ts_rltick = ticks;
1903060563ecSJulian Elischer 	td->td_lastcpu = td->td_oncpu;
1904060563ecSJulian Elischer 	td->td_oncpu = NOCPU;
1905ad9dadc4SAndriy Gapon 	preempted = (td->td_flags & TDF_SLICEEND) == 0 &&
1906ad9dadc4SAndriy Gapon 	    (flags & SW_PREEMPT) != 0;
19073d7f4117SAlexander Motin 	td->td_flags &= ~(TDF_NEEDRESCHED | TDF_SLICEEND);
190877918643SStephan Uphoff 	td->td_owepreempt = 0;
19092c27cb3aSAlexander Motin 	if (!TD_IS_IDLETHREAD(td))
19101690c6c1SJeff Roberson 		tdq->tdq_switchcnt++;
1911b11fdad0SJeff Roberson 	/*
1912ae7a6b38SJeff Roberson 	 * The lock pointer in an idle thread should never change.  Reset it
1913ae7a6b38SJeff Roberson 	 * to CAN_RUN as well.
1914b11fdad0SJeff Roberson 	 */
1915486a9414SJulian Elischer 	if (TD_IS_IDLETHREAD(td)) {
1916ae7a6b38SJeff Roberson 		MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1917bf0acc27SJohn Baldwin 		TD_SET_CAN_RUN(td);
19187b20fb19SJeff Roberson 	} else if (TD_IS_RUNNING(td)) {
1919ae7a6b38SJeff Roberson 		MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
19203d7f4117SAlexander Motin 		srqflag = preempted ?
1921598b368dSJeff Roberson 		    SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
1922c47f202bSJeff Roberson 		    SRQ_OURSELF|SRQ_YIELDING;
1923ba4932b5SMatthew D Fleming #ifdef SMP
19240f7a0ebdSMatthew D Fleming 		if (THREAD_CAN_MIGRATE(td) && !THREAD_CAN_SCHED(td, ts->ts_cpu))
19250f7a0ebdSMatthew D Fleming 			ts->ts_cpu = sched_pickcpu(td, 0);
1926ba4932b5SMatthew D Fleming #endif
1927c47f202bSJeff Roberson 		if (ts->ts_cpu == cpuid)
19289727e637SJeff Roberson 			tdq_runq_add(tdq, td, srqflag);
19290f7a0ebdSMatthew D Fleming 		else {
19300f7a0ebdSMatthew D Fleming 			KASSERT(THREAD_CAN_MIGRATE(td) ||
19310f7a0ebdSMatthew D Fleming 			    (ts->ts_flags & TSF_BOUND) != 0,
19320f7a0ebdSMatthew D Fleming 			    ("Thread %p shouldn't migrate", td));
1933c47f202bSJeff Roberson 			mtx = sched_switch_migrate(tdq, td, srqflag);
19340f7a0ebdSMatthew D Fleming 		}
1935ae7a6b38SJeff Roberson 	} else {
1936ae7a6b38SJeff Roberson 		/* This thread must be going to sleep. */
1937ae7a6b38SJeff Roberson 		TDQ_LOCK(tdq);
1938b0b9dee5SAttilio Rao 		mtx = thread_lock_block(td);
19399727e637SJeff Roberson 		tdq_load_rem(tdq, td);
1940ae7a6b38SJeff Roberson 	}
1941ae7a6b38SJeff Roberson 	/*
1942ae7a6b38SJeff Roberson 	 * We enter here with the thread blocked and assigned to the
1943ae7a6b38SJeff Roberson 	 * appropriate cpu run-queue or sleep-queue and with the current
1944ae7a6b38SJeff Roberson 	 * thread-queue locked.
1945ae7a6b38SJeff Roberson 	 */
1946ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED | MA_NOTRECURSED);
19472454aaf5SJeff Roberson 	newtd = choosethread();
1948ae7a6b38SJeff Roberson 	/*
1949ae7a6b38SJeff Roberson 	 * Call the MD code to switch contexts if necessary.
1950ae7a6b38SJeff Roberson 	 */
1951ebccf1e3SJoseph Koshy 	if (td != newtd) {
1952ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
1953ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1954ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
1955ebccf1e3SJoseph Koshy #endif
1956d9fae5abSAndriy Gapon 		SDT_PROBE2(sched, , , off__cpu, newtd, newtd->td_proc);
1957eea4f254SJeff Roberson 		lock_profile_release_lock(&TDQ_LOCKPTR(tdq)->lock_object);
195859c68134SJeff Roberson 		TDQ_LOCKPTR(tdq)->mtx_lock = (uintptr_t)newtd;
195993ccd6bfSKonstantin Belousov 		sched_pctcpu_update(td_get_sched(newtd), 0);
19606f5f25e5SJohn Birrell 
19616f5f25e5SJohn Birrell #ifdef KDTRACE_HOOKS
19626f5f25e5SJohn Birrell 		/*
19636f5f25e5SJohn Birrell 		 * If DTrace has set the active vtime enum to anything
19646f5f25e5SJohn Birrell 		 * other than INACTIVE (0), then it should have set the
19656f5f25e5SJohn Birrell 		 * function to call.
19666f5f25e5SJohn Birrell 		 */
19676f5f25e5SJohn Birrell 		if (dtrace_vtime_active)
19686f5f25e5SJohn Birrell 			(*dtrace_vtime_switch_func)(newtd);
19696f5f25e5SJohn Birrell #endif
19706f5f25e5SJohn Birrell 
1971ae7a6b38SJeff Roberson 		cpu_switch(td, newtd, mtx);
1972ae7a6b38SJeff Roberson 		/*
1973ae7a6b38SJeff Roberson 		 * We may return from cpu_switch on a different cpu.  However,
1974ae7a6b38SJeff Roberson 		 * we always return with td_lock pointing to the current cpu's
1975ae7a6b38SJeff Roberson 		 * run queue lock.
1976ae7a6b38SJeff Roberson 		 */
1977ae7a6b38SJeff Roberson 		cpuid = PCPU_GET(cpuid);
1978ae7a6b38SJeff Roberson 		tdq = TDQ_CPU(cpuid);
1979eea4f254SJeff Roberson 		lock_profile_obtain_lock_success(
1980eea4f254SJeff Roberson 		    &TDQ_LOCKPTR(tdq)->lock_object, 0, 0, __FILE__, __LINE__);
1981b3e9e682SRyan Stone 
1982d9fae5abSAndriy Gapon 		SDT_PROBE0(sched, , , on__cpu);
1983ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
1984ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
1985ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
1986ebccf1e3SJoseph Koshy #endif
1987b3e9e682SRyan Stone 	} else {
1988ae7a6b38SJeff Roberson 		thread_unblock_switch(td, mtx);
1989d9fae5abSAndriy Gapon 		SDT_PROBE0(sched, , , remain__cpu);
1990b3e9e682SRyan Stone 	}
1991ae7a6b38SJeff Roberson 	/*
1992ae7a6b38SJeff Roberson 	 * Assert that all went well and return.
1993ae7a6b38SJeff Roberson 	 */
1994ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED|MA_NOTRECURSED);
1995ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
1996ae7a6b38SJeff Roberson 	td->td_oncpu = cpuid;
199735e6168fSJeff Roberson }
199835e6168fSJeff Roberson 
1999ae7a6b38SJeff Roberson /*
2000ae7a6b38SJeff Roberson  * Adjust thread priorities as a result of a nice request.
2001ae7a6b38SJeff Roberson  */
200235e6168fSJeff Roberson void
2003fa885116SJulian Elischer sched_nice(struct proc *p, int nice)
200435e6168fSJeff Roberson {
200535e6168fSJeff Roberson 	struct thread *td;
200635e6168fSJeff Roberson 
2007fa885116SJulian Elischer 	PROC_LOCK_ASSERT(p, MA_OWNED);
2008e7d50326SJeff Roberson 
2009fa885116SJulian Elischer 	p->p_nice = nice;
20108460a577SJohn Birrell 	FOREACH_THREAD_IN_PROC(p, td) {
20117b20fb19SJeff Roberson 		thread_lock(td);
20128460a577SJohn Birrell 		sched_priority(td);
2013e7d50326SJeff Roberson 		sched_prio(td, td->td_base_user_pri);
20147b20fb19SJeff Roberson 		thread_unlock(td);
201535e6168fSJeff Roberson 	}
2016fa885116SJulian Elischer }
201735e6168fSJeff Roberson 
2018ae7a6b38SJeff Roberson /*
2019ae7a6b38SJeff Roberson  * Record the sleep time for the interactivity scorer.
2020ae7a6b38SJeff Roberson  */
202135e6168fSJeff Roberson void
2022c5aa6b58SJeff Roberson sched_sleep(struct thread *td, int prio)
202335e6168fSJeff Roberson {
2024e7d50326SJeff Roberson 
20257b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
202635e6168fSJeff Roberson 
202754b0e65fSJeff Roberson 	td->td_slptick = ticks;
202817c4c356SKonstantin Belousov 	if (TD_IS_SUSPENDED(td) || prio >= PSOCK)
2029c5aa6b58SJeff Roberson 		td->td_flags |= TDF_CANSWAP;
20302dc29adbSJohn Baldwin 	if (PRI_BASE(td->td_pri_class) != PRI_TIMESHARE)
20312dc29adbSJohn Baldwin 		return;
20320502fe2eSJeff Roberson 	if (static_boost == 1 && prio)
2033c5aa6b58SJeff Roberson 		sched_prio(td, prio);
20340502fe2eSJeff Roberson 	else if (static_boost && td->td_priority > static_boost)
20350502fe2eSJeff Roberson 		sched_prio(td, static_boost);
203635e6168fSJeff Roberson }
203735e6168fSJeff Roberson 
2038ae7a6b38SJeff Roberson /*
2039ae7a6b38SJeff Roberson  * Schedule a thread to resume execution and record how long it voluntarily
2040ae7a6b38SJeff Roberson  * slept.  We also update the pctcpu, interactivity, and priority.
2041ae7a6b38SJeff Roberson  */
204235e6168fSJeff Roberson void
204335e6168fSJeff Roberson sched_wakeup(struct thread *td)
204435e6168fSJeff Roberson {
204514618990SJeff Roberson 	struct td_sched *ts;
2046ae7a6b38SJeff Roberson 	int slptick;
2047e7d50326SJeff Roberson 
20487b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
204993ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
2050c5aa6b58SJeff Roberson 	td->td_flags &= ~TDF_CANSWAP;
205135e6168fSJeff Roberson 	/*
2052e7d50326SJeff Roberson 	 * If we slept for more than a tick update our interactivity and
2053e7d50326SJeff Roberson 	 * priority.
205435e6168fSJeff Roberson 	 */
205554b0e65fSJeff Roberson 	slptick = td->td_slptick;
205654b0e65fSJeff Roberson 	td->td_slptick = 0;
2057ae7a6b38SJeff Roberson 	if (slptick && slptick != ticks) {
20587295465eSAlexander Motin 		ts->ts_slptime += (ticks - slptick) << SCHED_TICK_SHIFT;
20598460a577SJohn Birrell 		sched_interact_update(td);
20607295465eSAlexander Motin 		sched_pctcpu_update(ts, 0);
2061f1e8dc4aSJeff Roberson 	}
20625e5c3873SJeff Roberson 	/*
20635e5c3873SJeff Roberson 	 * Reset the slice value since we slept and advanced the round-robin.
20645e5c3873SJeff Roberson 	 */
20655e5c3873SJeff Roberson 	ts->ts_slice = 0;
20667a5e5e2aSJeff Roberson 	sched_add(td, SRQ_BORING);
206735e6168fSJeff Roberson }
206835e6168fSJeff Roberson 
206935e6168fSJeff Roberson /*
207035e6168fSJeff Roberson  * Penalize the parent for creating a new child and initialize the child's
207135e6168fSJeff Roberson  * priority.
207235e6168fSJeff Roberson  */
207335e6168fSJeff Roberson void
20748460a577SJohn Birrell sched_fork(struct thread *td, struct thread *child)
207515dc847eSJeff Roberson {
20767b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
207793ccd6bfSKonstantin Belousov 	sched_pctcpu_update(td_get_sched(td), 1);
2078ad1e7d28SJulian Elischer 	sched_fork_thread(td, child);
2079e7d50326SJeff Roberson 	/*
2080e7d50326SJeff Roberson 	 * Penalize the parent and child for forking.
2081e7d50326SJeff Roberson 	 */
2082e7d50326SJeff Roberson 	sched_interact_fork(child);
2083e7d50326SJeff Roberson 	sched_priority(child);
208493ccd6bfSKonstantin Belousov 	td_get_sched(td)->ts_runtime += tickincr;
2085e7d50326SJeff Roberson 	sched_interact_update(td);
2086e7d50326SJeff Roberson 	sched_priority(td);
2087ad1e7d28SJulian Elischer }
2088ad1e7d28SJulian Elischer 
2089ae7a6b38SJeff Roberson /*
2090ae7a6b38SJeff Roberson  * Fork a new thread, may be within the same process.
2091ae7a6b38SJeff Roberson  */
2092ad1e7d28SJulian Elischer void
2093ad1e7d28SJulian Elischer sched_fork_thread(struct thread *td, struct thread *child)
2094ad1e7d28SJulian Elischer {
2095ad1e7d28SJulian Elischer 	struct td_sched *ts;
2096ad1e7d28SJulian Elischer 	struct td_sched *ts2;
20975e5c3873SJeff Roberson 	struct tdq *tdq;
20988460a577SJohn Birrell 
20995e5c3873SJeff Roberson 	tdq = TDQ_SELF();
21008b16c208SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2101e7d50326SJeff Roberson 	/*
2102e7d50326SJeff Roberson 	 * Initialize child.
2103e7d50326SJeff Roberson 	 */
210493ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
210593ccd6bfSKonstantin Belousov 	ts2 = td_get_sched(child);
210692de34dfSJohn Baldwin 	child->td_oncpu = NOCPU;
210792de34dfSJohn Baldwin 	child->td_lastcpu = NOCPU;
21085e5c3873SJeff Roberson 	child->td_lock = TDQ_LOCKPTR(tdq);
21098b16c208SJeff Roberson 	child->td_cpuset = cpuset_ref(td->td_cpuset);
2110ad1e7d28SJulian Elischer 	ts2->ts_cpu = ts->ts_cpu;
21118b16c208SJeff Roberson 	ts2->ts_flags = 0;
2112e7d50326SJeff Roberson 	/*
211322d19207SJohn Baldwin 	 * Grab our parents cpu estimation information.
2114e7d50326SJeff Roberson 	 */
2115ad1e7d28SJulian Elischer 	ts2->ts_ticks = ts->ts_ticks;
2116ad1e7d28SJulian Elischer 	ts2->ts_ltick = ts->ts_ltick;
2117ad1e7d28SJulian Elischer 	ts2->ts_ftick = ts->ts_ftick;
211822d19207SJohn Baldwin 	/*
211922d19207SJohn Baldwin 	 * Do not inherit any borrowed priority from the parent.
212022d19207SJohn Baldwin 	 */
212122d19207SJohn Baldwin 	child->td_priority = child->td_base_pri;
2122e7d50326SJeff Roberson 	/*
2123e7d50326SJeff Roberson 	 * And update interactivity score.
2124e7d50326SJeff Roberson 	 */
2125ae7a6b38SJeff Roberson 	ts2->ts_slptime = ts->ts_slptime;
2126ae7a6b38SJeff Roberson 	ts2->ts_runtime = ts->ts_runtime;
21275e5c3873SJeff Roberson 	/* Attempt to quickly learn interactivity. */
21285e5c3873SJeff Roberson 	ts2->ts_slice = tdq_slice(tdq) - sched_slice_min;
21298f51ad55SJeff Roberson #ifdef KTR
21308f51ad55SJeff Roberson 	bzero(ts2->ts_name, sizeof(ts2->ts_name));
21318f51ad55SJeff Roberson #endif
213215dc847eSJeff Roberson }
213315dc847eSJeff Roberson 
2134ae7a6b38SJeff Roberson /*
2135ae7a6b38SJeff Roberson  * Adjust the priority class of a thread.
2136ae7a6b38SJeff Roberson  */
213715dc847eSJeff Roberson void
21388460a577SJohn Birrell sched_class(struct thread *td, int class)
213915dc847eSJeff Roberson {
214015dc847eSJeff Roberson 
21417b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
21428460a577SJohn Birrell 	if (td->td_pri_class == class)
214315dc847eSJeff Roberson 		return;
21448460a577SJohn Birrell 	td->td_pri_class = class;
214535e6168fSJeff Roberson }
214635e6168fSJeff Roberson 
214735e6168fSJeff Roberson /*
214835e6168fSJeff Roberson  * Return some of the child's priority and interactivity to the parent.
214935e6168fSJeff Roberson  */
215035e6168fSJeff Roberson void
2151fc6c30f6SJulian Elischer sched_exit(struct proc *p, struct thread *child)
215235e6168fSJeff Roberson {
2153e7d50326SJeff Roberson 	struct thread *td;
2154141ad61cSJeff Roberson 
21558f51ad55SJeff Roberson 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(child), "proc exit",
2156cd39bb09SXin LI 	    "prio:%d", child->td_priority);
2157374ae2a3SJeff Roberson 	PROC_LOCK_ASSERT(p, MA_OWNED);
2158e7d50326SJeff Roberson 	td = FIRST_THREAD_IN_PROC(p);
2159e7d50326SJeff Roberson 	sched_exit_thread(td, child);
2160ad1e7d28SJulian Elischer }
2161ad1e7d28SJulian Elischer 
2162ae7a6b38SJeff Roberson /*
2163ae7a6b38SJeff Roberson  * Penalize another thread for the time spent on this one.  This helps to
2164ae7a6b38SJeff Roberson  * worsen the priority and interactivity of processes which schedule batch
2165ae7a6b38SJeff Roberson  * jobs such as make.  This has little effect on the make process itself but
2166ae7a6b38SJeff Roberson  * causes new processes spawned by it to receive worse scores immediately.
2167ae7a6b38SJeff Roberson  */
2168ad1e7d28SJulian Elischer void
2169fc6c30f6SJulian Elischer sched_exit_thread(struct thread *td, struct thread *child)
2170ad1e7d28SJulian Elischer {
2171fc6c30f6SJulian Elischer 
21728f51ad55SJeff Roberson 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(child), "thread exit",
2173cd39bb09SXin LI 	    "prio:%d", child->td_priority);
2174e7d50326SJeff Roberson 	/*
2175e7d50326SJeff Roberson 	 * Give the child's runtime to the parent without returning the
2176e7d50326SJeff Roberson 	 * sleep time as a penalty to the parent.  This causes shells that
2177e7d50326SJeff Roberson 	 * launch expensive things to mark their children as expensive.
2178e7d50326SJeff Roberson 	 */
21797b20fb19SJeff Roberson 	thread_lock(td);
218093ccd6bfSKonstantin Belousov 	td_get_sched(td)->ts_runtime += td_get_sched(child)->ts_runtime;
2181fc6c30f6SJulian Elischer 	sched_interact_update(td);
2182e7d50326SJeff Roberson 	sched_priority(td);
21837b20fb19SJeff Roberson 	thread_unlock(td);
2184ad1e7d28SJulian Elischer }
2185ad1e7d28SJulian Elischer 
2186ff256d9cSJeff Roberson void
2187ff256d9cSJeff Roberson sched_preempt(struct thread *td)
2188ff256d9cSJeff Roberson {
2189ff256d9cSJeff Roberson 	struct tdq *tdq;
2190ff256d9cSJeff Roberson 
2191b3e9e682SRyan Stone 	SDT_PROBE2(sched, , , surrender, td, td->td_proc);
2192b3e9e682SRyan Stone 
2193ff256d9cSJeff Roberson 	thread_lock(td);
2194ff256d9cSJeff Roberson 	tdq = TDQ_SELF();
2195ff256d9cSJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2196ff256d9cSJeff Roberson 	tdq->tdq_ipipending = 0;
2197ff256d9cSJeff Roberson 	if (td->td_priority > tdq->tdq_lowpri) {
21988df78c41SJeff Roberson 		int flags;
21998df78c41SJeff Roberson 
22008df78c41SJeff Roberson 		flags = SW_INVOL | SW_PREEMPT;
2201ff256d9cSJeff Roberson 		if (td->td_critnest > 1)
2202ff256d9cSJeff Roberson 			td->td_owepreempt = 1;
22038df78c41SJeff Roberson 		else if (TD_IS_IDLETHREAD(td))
22048df78c41SJeff Roberson 			mi_switch(flags | SWT_REMOTEWAKEIDLE, NULL);
2205ff256d9cSJeff Roberson 		else
22068df78c41SJeff Roberson 			mi_switch(flags | SWT_REMOTEPREEMPT, NULL);
2207ff256d9cSJeff Roberson 	}
2208ff256d9cSJeff Roberson 	thread_unlock(td);
2209ff256d9cSJeff Roberson }
2210ff256d9cSJeff Roberson 
2211ae7a6b38SJeff Roberson /*
2212ae7a6b38SJeff Roberson  * Fix priorities on return to user-space.  Priorities may be elevated due
2213ae7a6b38SJeff Roberson  * to static priorities in msleep() or similar.
2214ae7a6b38SJeff Roberson  */
2215ad1e7d28SJulian Elischer void
2216ad1e7d28SJulian Elischer sched_userret(struct thread *td)
2217ad1e7d28SJulian Elischer {
2218ad1e7d28SJulian Elischer 	/*
2219ad1e7d28SJulian Elischer 	 * XXX we cheat slightly on the locking here to avoid locking in
2220ad1e7d28SJulian Elischer 	 * the usual case.  Setting td_priority here is essentially an
2221ad1e7d28SJulian Elischer 	 * incomplete workaround for not setting it properly elsewhere.
2222ad1e7d28SJulian Elischer 	 * Now that some interrupt handlers are threads, not setting it
2223ad1e7d28SJulian Elischer 	 * properly elsewhere can clobber it in the window between setting
2224ad1e7d28SJulian Elischer 	 * it here and returning to user mode, so don't waste time setting
2225ad1e7d28SJulian Elischer 	 * it perfectly here.
2226ad1e7d28SJulian Elischer 	 */
2227ad1e7d28SJulian Elischer 	KASSERT((td->td_flags & TDF_BORROWING) == 0,
2228ad1e7d28SJulian Elischer 	    ("thread with borrowed priority returning to userland"));
2229ad1e7d28SJulian Elischer 	if (td->td_priority != td->td_user_pri) {
22307b20fb19SJeff Roberson 		thread_lock(td);
2231ad1e7d28SJulian Elischer 		td->td_priority = td->td_user_pri;
2232ad1e7d28SJulian Elischer 		td->td_base_pri = td->td_user_pri;
223362fa74d9SJeff Roberson 		tdq_setlowpri(TDQ_SELF(), td);
22347b20fb19SJeff Roberson 		thread_unlock(td);
2235ad1e7d28SJulian Elischer         }
223635e6168fSJeff Roberson }
223735e6168fSJeff Roberson 
2238ae7a6b38SJeff Roberson /*
2239ae7a6b38SJeff Roberson  * Handle a stathz tick.  This is really only relevant for timeshare
2240ae7a6b38SJeff Roberson  * threads.
2241ae7a6b38SJeff Roberson  */
224235e6168fSJeff Roberson void
22437cf90fb3SJeff Roberson sched_clock(struct thread *td)
224435e6168fSJeff Roberson {
2245ad1e7d28SJulian Elischer 	struct tdq *tdq;
2246ad1e7d28SJulian Elischer 	struct td_sched *ts;
224735e6168fSJeff Roberson 
2248ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
22493f872f85SJeff Roberson 	tdq = TDQ_SELF();
22507fcf154aSJeff Roberson #ifdef SMP
22517fcf154aSJeff Roberson 	/*
22527fcf154aSJeff Roberson 	 * We run the long term load balancer infrequently on the first cpu.
22537fcf154aSJeff Roberson 	 */
22547fcf154aSJeff Roberson 	if (balance_tdq == tdq) {
22557fcf154aSJeff Roberson 		if (balance_ticks && --balance_ticks == 0)
22567fcf154aSJeff Roberson 			sched_balance();
22577fcf154aSJeff Roberson 	}
22587fcf154aSJeff Roberson #endif
22593f872f85SJeff Roberson 	/*
22601690c6c1SJeff Roberson 	 * Save the old switch count so we have a record of the last ticks
22611690c6c1SJeff Roberson 	 * activity.   Initialize the new switch count based on our load.
22621690c6c1SJeff Roberson 	 * If there is some activity seed it to reflect that.
22631690c6c1SJeff Roberson 	 */
22641690c6c1SJeff Roberson 	tdq->tdq_oldswitchcnt = tdq->tdq_switchcnt;
22656c47aaaeSJeff Roberson 	tdq->tdq_switchcnt = tdq->tdq_load;
22661690c6c1SJeff Roberson 	/*
22673f872f85SJeff Roberson 	 * Advance the insert index once for each tick to ensure that all
22683f872f85SJeff Roberson 	 * threads get a chance to run.
22693f872f85SJeff Roberson 	 */
22703f872f85SJeff Roberson 	if (tdq->tdq_idx == tdq->tdq_ridx) {
22713f872f85SJeff Roberson 		tdq->tdq_idx = (tdq->tdq_idx + 1) % RQ_NQS;
22723f872f85SJeff Roberson 		if (TAILQ_EMPTY(&tdq->tdq_timeshare.rq_queues[tdq->tdq_ridx]))
22733f872f85SJeff Roberson 			tdq->tdq_ridx = tdq->tdq_idx;
22743f872f85SJeff Roberson 	}
227593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
22767295465eSAlexander Motin 	sched_pctcpu_update(ts, 1);
2277fd0b8c78SJeff Roberson 	if (td->td_pri_class & PRI_FIFO_BIT)
2278a8949de2SJeff Roberson 		return;
2279c9a8cba4SJohn Baldwin 	if (PRI_BASE(td->td_pri_class) == PRI_TIMESHARE) {
2280a8949de2SJeff Roberson 		/*
2281fd0b8c78SJeff Roberson 		 * We used a tick; charge it to the thread so
2282fd0b8c78SJeff Roberson 		 * that we can compute our interactivity.
228315dc847eSJeff Roberson 		 */
228493ccd6bfSKonstantin Belousov 		td_get_sched(td)->ts_runtime += tickincr;
22858460a577SJohn Birrell 		sched_interact_update(td);
228673daf66fSJeff Roberson 		sched_priority(td);
2287fd0b8c78SJeff Roberson 	}
2288579895dfSAlexander Motin 
228935e6168fSJeff Roberson 	/*
2290579895dfSAlexander Motin 	 * Force a context switch if the current thread has used up a full
2291579895dfSAlexander Motin 	 * time slice (default is 100ms).
229235e6168fSJeff Roberson 	 */
22935e5c3873SJeff Roberson 	if (!TD_IS_IDLETHREAD(td) && ++ts->ts_slice >= tdq_slice(tdq)) {
22945e5c3873SJeff Roberson 		ts->ts_slice = 0;
22953d7f4117SAlexander Motin 		td->td_flags |= TDF_NEEDRESCHED | TDF_SLICEEND;
229635e6168fSJeff Roberson 	}
2297579895dfSAlexander Motin }
229835e6168fSJeff Roberson 
2299ccd0ec40SKonstantin Belousov u_int
2300ccd0ec40SKonstantin Belousov sched_estcpu(struct thread *td __unused)
2301ae7a6b38SJeff Roberson {
2302ae7a6b38SJeff Roberson 
2303ccd0ec40SKonstantin Belousov 	return (0);
2304ae7a6b38SJeff Roberson }
2305ae7a6b38SJeff Roberson 
2306ae7a6b38SJeff Roberson /*
2307ae7a6b38SJeff Roberson  * Return whether the current CPU has runnable tasks.  Used for in-kernel
2308ae7a6b38SJeff Roberson  * cooperative idle threads.
2309ae7a6b38SJeff Roberson  */
231035e6168fSJeff Roberson int
231135e6168fSJeff Roberson sched_runnable(void)
231235e6168fSJeff Roberson {
2313ad1e7d28SJulian Elischer 	struct tdq *tdq;
2314b90816f1SJeff Roberson 	int load;
231535e6168fSJeff Roberson 
2316b90816f1SJeff Roberson 	load = 1;
2317b90816f1SJeff Roberson 
2318ad1e7d28SJulian Elischer 	tdq = TDQ_SELF();
23193f741ca1SJeff Roberson 	if ((curthread->td_flags & TDF_IDLETD) != 0) {
2320d2ad694cSJeff Roberson 		if (tdq->tdq_load > 0)
23213f741ca1SJeff Roberson 			goto out;
23223f741ca1SJeff Roberson 	} else
2323d2ad694cSJeff Roberson 		if (tdq->tdq_load - 1 > 0)
2324b90816f1SJeff Roberson 			goto out;
2325b90816f1SJeff Roberson 	load = 0;
2326b90816f1SJeff Roberson out:
2327b90816f1SJeff Roberson 	return (load);
232835e6168fSJeff Roberson }
232935e6168fSJeff Roberson 
2330ae7a6b38SJeff Roberson /*
2331ae7a6b38SJeff Roberson  * Choose the highest priority thread to run.  The thread is removed from
2332ae7a6b38SJeff Roberson  * the run-queue while running however the load remains.  For SMP we set
2333ae7a6b38SJeff Roberson  * the tdq in the global idle bitmask if it idles here.
2334ae7a6b38SJeff Roberson  */
23357a5e5e2aSJeff Roberson struct thread *
2336c9f25d8fSJeff Roberson sched_choose(void)
2337c9f25d8fSJeff Roberson {
23389727e637SJeff Roberson 	struct thread *td;
2339ae7a6b38SJeff Roberson 	struct tdq *tdq;
2340ae7a6b38SJeff Roberson 
2341ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2342ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
23439727e637SJeff Roberson 	td = tdq_choose(tdq);
23449727e637SJeff Roberson 	if (td) {
23459727e637SJeff Roberson 		tdq_runq_rem(tdq, td);
23460502fe2eSJeff Roberson 		tdq->tdq_lowpri = td->td_priority;
23479727e637SJeff Roberson 		return (td);
234835e6168fSJeff Roberson 	}
23490502fe2eSJeff Roberson 	tdq->tdq_lowpri = PRI_MAX_IDLE;
235062fa74d9SJeff Roberson 	return (PCPU_GET(idlethread));
23517a5e5e2aSJeff Roberson }
23527a5e5e2aSJeff Roberson 
2353ae7a6b38SJeff Roberson /*
2354ae7a6b38SJeff Roberson  * Set owepreempt if necessary.  Preemption never happens directly in ULE,
2355ae7a6b38SJeff Roberson  * we always request it once we exit a critical section.
2356ae7a6b38SJeff Roberson  */
2357ae7a6b38SJeff Roberson static inline void
2358ae7a6b38SJeff Roberson sched_setpreempt(struct thread *td)
23597a5e5e2aSJeff Roberson {
23607a5e5e2aSJeff Roberson 	struct thread *ctd;
23617a5e5e2aSJeff Roberson 	int cpri;
23627a5e5e2aSJeff Roberson 	int pri;
23637a5e5e2aSJeff Roberson 
2364ff256d9cSJeff Roberson 	THREAD_LOCK_ASSERT(curthread, MA_OWNED);
2365ff256d9cSJeff Roberson 
23667a5e5e2aSJeff Roberson 	ctd = curthread;
23677a5e5e2aSJeff Roberson 	pri = td->td_priority;
23687a5e5e2aSJeff Roberson 	cpri = ctd->td_priority;
2369ff256d9cSJeff Roberson 	if (pri < cpri)
2370ff256d9cSJeff Roberson 		ctd->td_flags |= TDF_NEEDRESCHED;
23717a5e5e2aSJeff Roberson 	if (panicstr != NULL || pri >= cpri || cold || TD_IS_INHIBITED(ctd))
2372ae7a6b38SJeff Roberson 		return;
2373ff256d9cSJeff Roberson 	if (!sched_shouldpreempt(pri, cpri, 0))
2374ae7a6b38SJeff Roberson 		return;
23757a5e5e2aSJeff Roberson 	ctd->td_owepreempt = 1;
237635e6168fSJeff Roberson }
237735e6168fSJeff Roberson 
2378ae7a6b38SJeff Roberson /*
237973daf66fSJeff Roberson  * Add a thread to a thread queue.  Select the appropriate runq and add the
238073daf66fSJeff Roberson  * thread to it.  This is the internal function called when the tdq is
238173daf66fSJeff Roberson  * predetermined.
2382ae7a6b38SJeff Roberson  */
238335e6168fSJeff Roberson void
2384ae7a6b38SJeff Roberson tdq_add(struct tdq *tdq, struct thread *td, int flags)
238535e6168fSJeff Roberson {
2386c9f25d8fSJeff Roberson 
2387ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
23887a5e5e2aSJeff Roberson 	KASSERT((td->td_inhibitors == 0),
23897a5e5e2aSJeff Roberson 	    ("sched_add: trying to run inhibited thread"));
23907a5e5e2aSJeff Roberson 	KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
23917a5e5e2aSJeff Roberson 	    ("sched_add: bad thread state"));
2392b61ce5b0SJeff Roberson 	KASSERT(td->td_flags & TDF_INMEM,
2393b61ce5b0SJeff Roberson 	    ("sched_add: thread swapped out"));
2394ae7a6b38SJeff Roberson 
2395ae7a6b38SJeff Roberson 	if (td->td_priority < tdq->tdq_lowpri)
2396ae7a6b38SJeff Roberson 		tdq->tdq_lowpri = td->td_priority;
23979727e637SJeff Roberson 	tdq_runq_add(tdq, td, flags);
23989727e637SJeff Roberson 	tdq_load_add(tdq, td);
2399ae7a6b38SJeff Roberson }
2400ae7a6b38SJeff Roberson 
2401ae7a6b38SJeff Roberson /*
2402ae7a6b38SJeff Roberson  * Select the target thread queue and add a thread to it.  Request
2403ae7a6b38SJeff Roberson  * preemption or IPI a remote processor if required.
2404ae7a6b38SJeff Roberson  */
2405ae7a6b38SJeff Roberson void
2406ae7a6b38SJeff Roberson sched_add(struct thread *td, int flags)
2407ae7a6b38SJeff Roberson {
2408ae7a6b38SJeff Roberson 	struct tdq *tdq;
24097b8bfa0dSJeff Roberson #ifdef SMP
2410ae7a6b38SJeff Roberson 	int cpu;
2411ae7a6b38SJeff Roberson #endif
24128f51ad55SJeff Roberson 
24138f51ad55SJeff Roberson 	KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq add",
24148f51ad55SJeff Roberson 	    "prio:%d", td->td_priority, KTR_ATTR_LINKED,
24158f51ad55SJeff Roberson 	    sched_tdname(curthread));
24168f51ad55SJeff Roberson 	KTR_POINT1(KTR_SCHED, "thread", sched_tdname(curthread), "wokeup",
24178f51ad55SJeff Roberson 	    KTR_ATTR_LINKED, sched_tdname(td));
2418b3e9e682SRyan Stone 	SDT_PROBE4(sched, , , enqueue, td, td->td_proc, NULL,
2419b3e9e682SRyan Stone 	    flags & SRQ_PREEMPTED);
2420ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2421ae7a6b38SJeff Roberson 	/*
2422ae7a6b38SJeff Roberson 	 * Recalculate the priority before we select the target cpu or
2423ae7a6b38SJeff Roberson 	 * run-queue.
2424ae7a6b38SJeff Roberson 	 */
2425ae7a6b38SJeff Roberson 	if (PRI_BASE(td->td_pri_class) == PRI_TIMESHARE)
2426ae7a6b38SJeff Roberson 		sched_priority(td);
2427ae7a6b38SJeff Roberson #ifdef SMP
2428ae7a6b38SJeff Roberson 	/*
2429ae7a6b38SJeff Roberson 	 * Pick the destination cpu and if it isn't ours transfer to the
2430ae7a6b38SJeff Roberson 	 * target cpu.
2431ae7a6b38SJeff Roberson 	 */
24329727e637SJeff Roberson 	cpu = sched_pickcpu(td, flags);
24339727e637SJeff Roberson 	tdq = sched_setcpu(td, cpu, flags);
2434ae7a6b38SJeff Roberson 	tdq_add(tdq, td, flags);
243573daf66fSJeff Roberson 	if (cpu != PCPU_GET(cpuid)) {
243627ee18adSRyan Stone 		tdq_notify(tdq, td);
24377b8bfa0dSJeff Roberson 		return;
24387b8bfa0dSJeff Roberson 	}
2439ae7a6b38SJeff Roberson #else
2440ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2441ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
2442ae7a6b38SJeff Roberson 	/*
2443ae7a6b38SJeff Roberson 	 * Now that the thread is moving to the run-queue, set the lock
2444ae7a6b38SJeff Roberson 	 * to the scheduler's lock.
2445ae7a6b38SJeff Roberson 	 */
2446ae7a6b38SJeff Roberson 	thread_lock_set(td, TDQ_LOCKPTR(tdq));
2447ae7a6b38SJeff Roberson 	tdq_add(tdq, td, flags);
24487b8bfa0dSJeff Roberson #endif
2449ae7a6b38SJeff Roberson 	if (!(flags & SRQ_YIELDING))
2450ae7a6b38SJeff Roberson 		sched_setpreempt(td);
245135e6168fSJeff Roberson }
245235e6168fSJeff Roberson 
2453ae7a6b38SJeff Roberson /*
2454ae7a6b38SJeff Roberson  * Remove a thread from a run-queue without running it.  This is used
2455ae7a6b38SJeff Roberson  * when we're stealing a thread from a remote queue.  Otherwise all threads
2456ae7a6b38SJeff Roberson  * exit by calling sched_exit_thread() and sched_throw() themselves.
2457ae7a6b38SJeff Roberson  */
245835e6168fSJeff Roberson void
24597cf90fb3SJeff Roberson sched_rem(struct thread *td)
246035e6168fSJeff Roberson {
2461ad1e7d28SJulian Elischer 	struct tdq *tdq;
24627cf90fb3SJeff Roberson 
24638f51ad55SJeff Roberson 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "runq rem",
24648f51ad55SJeff Roberson 	    "prio:%d", td->td_priority);
2465b3e9e682SRyan Stone 	SDT_PROBE3(sched, , , dequeue, td, td->td_proc, NULL);
246693ccd6bfSKonstantin Belousov 	tdq = TDQ_CPU(td_get_sched(td)->ts_cpu);
2467ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2468ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
24697a5e5e2aSJeff Roberson 	KASSERT(TD_ON_RUNQ(td),
2470ad1e7d28SJulian Elischer 	    ("sched_rem: thread not on run queue"));
24719727e637SJeff Roberson 	tdq_runq_rem(tdq, td);
24729727e637SJeff Roberson 	tdq_load_rem(tdq, td);
24737a5e5e2aSJeff Roberson 	TD_SET_CAN_RUN(td);
247462fa74d9SJeff Roberson 	if (td->td_priority == tdq->tdq_lowpri)
247562fa74d9SJeff Roberson 		tdq_setlowpri(tdq, NULL);
247635e6168fSJeff Roberson }
247735e6168fSJeff Roberson 
2478ae7a6b38SJeff Roberson /*
2479ae7a6b38SJeff Roberson  * Fetch cpu utilization information.  Updates on demand.
2480ae7a6b38SJeff Roberson  */
248135e6168fSJeff Roberson fixpt_t
24827cf90fb3SJeff Roberson sched_pctcpu(struct thread *td)
248335e6168fSJeff Roberson {
248435e6168fSJeff Roberson 	fixpt_t pctcpu;
2485ad1e7d28SJulian Elischer 	struct td_sched *ts;
248635e6168fSJeff Roberson 
248735e6168fSJeff Roberson 	pctcpu = 0;
248893ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
248935e6168fSJeff Roberson 
24903da35a0aSJohn Baldwin 	THREAD_LOCK_ASSERT(td, MA_OWNED);
24917295465eSAlexander Motin 	sched_pctcpu_update(ts, TD_IS_RUNNING(td));
2492ad1e7d28SJulian Elischer 	if (ts->ts_ticks) {
249335e6168fSJeff Roberson 		int rtick;
249435e6168fSJeff Roberson 
249535e6168fSJeff Roberson 		/* How many rtick per second ? */
2496e7d50326SJeff Roberson 		rtick = min(SCHED_TICK_HZ(ts) / SCHED_TICK_SECS, hz);
2497e7d50326SJeff Roberson 		pctcpu = (FSCALE * ((FSCALE * rtick)/hz)) >> FSHIFT;
249835e6168fSJeff Roberson 	}
249935e6168fSJeff Roberson 
250035e6168fSJeff Roberson 	return (pctcpu);
250135e6168fSJeff Roberson }
250235e6168fSJeff Roberson 
250362fa74d9SJeff Roberson /*
250462fa74d9SJeff Roberson  * Enforce affinity settings for a thread.  Called after adjustments to
250562fa74d9SJeff Roberson  * cpumask.
250662fa74d9SJeff Roberson  */
2507885d51a3SJeff Roberson void
2508885d51a3SJeff Roberson sched_affinity(struct thread *td)
2509885d51a3SJeff Roberson {
251062fa74d9SJeff Roberson #ifdef SMP
251162fa74d9SJeff Roberson 	struct td_sched *ts;
251262fa74d9SJeff Roberson 
251362fa74d9SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
251493ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
251562fa74d9SJeff Roberson 	if (THREAD_CAN_SCHED(td, ts->ts_cpu))
251662fa74d9SJeff Roberson 		return;
251753a6c8b3SJeff Roberson 	if (TD_ON_RUNQ(td)) {
251853a6c8b3SJeff Roberson 		sched_rem(td);
251953a6c8b3SJeff Roberson 		sched_add(td, SRQ_BORING);
252053a6c8b3SJeff Roberson 		return;
252153a6c8b3SJeff Roberson 	}
252262fa74d9SJeff Roberson 	if (!TD_IS_RUNNING(td))
252362fa74d9SJeff Roberson 		return;
252462fa74d9SJeff Roberson 	/*
25250f7a0ebdSMatthew D Fleming 	 * Force a switch before returning to userspace.  If the
25260f7a0ebdSMatthew D Fleming 	 * target thread is not running locally send an ipi to force
25270f7a0ebdSMatthew D Fleming 	 * the issue.
252862fa74d9SJeff Roberson 	 */
2529a8103ae8SJohn Baldwin 	td->td_flags |= TDF_NEEDRESCHED;
25300f7a0ebdSMatthew D Fleming 	if (td != curthread)
25310f7a0ebdSMatthew D Fleming 		ipi_cpu(ts->ts_cpu, IPI_PREEMPT);
253262fa74d9SJeff Roberson #endif
2533885d51a3SJeff Roberson }
2534885d51a3SJeff Roberson 
2535ae7a6b38SJeff Roberson /*
2536ae7a6b38SJeff Roberson  * Bind a thread to a target cpu.
2537ae7a6b38SJeff Roberson  */
25389bacd788SJeff Roberson void
25399bacd788SJeff Roberson sched_bind(struct thread *td, int cpu)
25409bacd788SJeff Roberson {
2541ad1e7d28SJulian Elischer 	struct td_sched *ts;
25429bacd788SJeff Roberson 
2543c47f202bSJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED|MA_NOTRECURSED);
25441d7830edSJohn Baldwin 	KASSERT(td == curthread, ("sched_bind: can only bind curthread"));
254593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
25466b2f763fSJeff Roberson 	if (ts->ts_flags & TSF_BOUND)
2547c95d2db2SJeff Roberson 		sched_unbind(td);
25480f7a0ebdSMatthew D Fleming 	KASSERT(THREAD_CAN_MIGRATE(td), ("%p must be migratable", td));
2549ad1e7d28SJulian Elischer 	ts->ts_flags |= TSF_BOUND;
25506b2f763fSJeff Roberson 	sched_pin();
255180f86c9fSJeff Roberson 	if (PCPU_GET(cpuid) == cpu)
25529bacd788SJeff Roberson 		return;
25536b2f763fSJeff Roberson 	ts->ts_cpu = cpu;
25549bacd788SJeff Roberson 	/* When we return from mi_switch we'll be on the correct cpu. */
2555279f949eSPoul-Henning Kamp 	mi_switch(SW_VOL, NULL);
25569bacd788SJeff Roberson }
25579bacd788SJeff Roberson 
2558ae7a6b38SJeff Roberson /*
2559ae7a6b38SJeff Roberson  * Release a bound thread.
2560ae7a6b38SJeff Roberson  */
25619bacd788SJeff Roberson void
25629bacd788SJeff Roberson sched_unbind(struct thread *td)
25639bacd788SJeff Roberson {
2564e7d50326SJeff Roberson 	struct td_sched *ts;
2565e7d50326SJeff Roberson 
25667b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
25671d7830edSJohn Baldwin 	KASSERT(td == curthread, ("sched_unbind: can only bind curthread"));
256893ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
25696b2f763fSJeff Roberson 	if ((ts->ts_flags & TSF_BOUND) == 0)
25706b2f763fSJeff Roberson 		return;
2571e7d50326SJeff Roberson 	ts->ts_flags &= ~TSF_BOUND;
2572e7d50326SJeff Roberson 	sched_unpin();
25739bacd788SJeff Roberson }
25749bacd788SJeff Roberson 
257535e6168fSJeff Roberson int
2576ebccf1e3SJoseph Koshy sched_is_bound(struct thread *td)
2577ebccf1e3SJoseph Koshy {
25787b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
257993ccd6bfSKonstantin Belousov 	return (td_get_sched(td)->ts_flags & TSF_BOUND);
2580ebccf1e3SJoseph Koshy }
2581ebccf1e3SJoseph Koshy 
2582ae7a6b38SJeff Roberson /*
2583ae7a6b38SJeff Roberson  * Basic yield call.
2584ae7a6b38SJeff Roberson  */
258536ec198bSDavid Xu void
258636ec198bSDavid Xu sched_relinquish(struct thread *td)
258736ec198bSDavid Xu {
25887b20fb19SJeff Roberson 	thread_lock(td);
25898df78c41SJeff Roberson 	mi_switch(SW_VOL | SWT_RELINQUISH, NULL);
25907b20fb19SJeff Roberson 	thread_unlock(td);
259136ec198bSDavid Xu }
259236ec198bSDavid Xu 
2593ae7a6b38SJeff Roberson /*
2594ae7a6b38SJeff Roberson  * Return the total system load.
2595ae7a6b38SJeff Roberson  */
2596ebccf1e3SJoseph Koshy int
259733916c36SJeff Roberson sched_load(void)
259833916c36SJeff Roberson {
259933916c36SJeff Roberson #ifdef SMP
260033916c36SJeff Roberson 	int total;
260133916c36SJeff Roberson 	int i;
260233916c36SJeff Roberson 
260333916c36SJeff Roberson 	total = 0;
26043aa6d94eSJohn Baldwin 	CPU_FOREACH(i)
260562fa74d9SJeff Roberson 		total += TDQ_CPU(i)->tdq_sysload;
260633916c36SJeff Roberson 	return (total);
260733916c36SJeff Roberson #else
2608d2ad694cSJeff Roberson 	return (TDQ_SELF()->tdq_sysload);
260933916c36SJeff Roberson #endif
261033916c36SJeff Roberson }
261133916c36SJeff Roberson 
261233916c36SJeff Roberson int
261335e6168fSJeff Roberson sched_sizeof_proc(void)
261435e6168fSJeff Roberson {
261535e6168fSJeff Roberson 	return (sizeof(struct proc));
261635e6168fSJeff Roberson }
261735e6168fSJeff Roberson 
261835e6168fSJeff Roberson int
261935e6168fSJeff Roberson sched_sizeof_thread(void)
262035e6168fSJeff Roberson {
262135e6168fSJeff Roberson 	return (sizeof(struct thread) + sizeof(struct td_sched));
262235e6168fSJeff Roberson }
2623b41f1452SDavid Xu 
262409c8a4ccSJeff Roberson #ifdef SMP
262509c8a4ccSJeff Roberson #define	TDQ_IDLESPIN(tdq)						\
262609c8a4ccSJeff Roberson     ((tdq)->tdq_cg != NULL && ((tdq)->tdq_cg->cg_flags & CG_FLAG_THREAD) == 0)
262709c8a4ccSJeff Roberson #else
262809c8a4ccSJeff Roberson #define	TDQ_IDLESPIN(tdq)	1
262909c8a4ccSJeff Roberson #endif
263009c8a4ccSJeff Roberson 
26317a5e5e2aSJeff Roberson /*
26327a5e5e2aSJeff Roberson  * The actual idle process.
26337a5e5e2aSJeff Roberson  */
26347a5e5e2aSJeff Roberson void
26357a5e5e2aSJeff Roberson sched_idletd(void *dummy)
26367a5e5e2aSJeff Roberson {
26377a5e5e2aSJeff Roberson 	struct thread *td;
2638ae7a6b38SJeff Roberson 	struct tdq *tdq;
26392c27cb3aSAlexander Motin 	int oldswitchcnt, switchcnt;
26401690c6c1SJeff Roberson 	int i;
26417a5e5e2aSJeff Roberson 
26427b55ab05SJeff Roberson 	mtx_assert(&Giant, MA_NOTOWNED);
26437a5e5e2aSJeff Roberson 	td = curthread;
2644ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2645ba96d2d8SJohn Baldwin 	THREAD_NO_SLEEPING();
26462c27cb3aSAlexander Motin 	oldswitchcnt = -1;
2647ae7a6b38SJeff Roberson 	for (;;) {
26482c27cb3aSAlexander Motin 		if (tdq->tdq_load) {
26492c27cb3aSAlexander Motin 			thread_lock(td);
26502c27cb3aSAlexander Motin 			mi_switch(SW_VOL | SWT_IDLE, NULL);
26512c27cb3aSAlexander Motin 			thread_unlock(td);
26522c27cb3aSAlexander Motin 		}
26532c27cb3aSAlexander Motin 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
2654ae7a6b38SJeff Roberson #ifdef SMP
26552c27cb3aSAlexander Motin 		if (switchcnt != oldswitchcnt) {
26562c27cb3aSAlexander Motin 			oldswitchcnt = switchcnt;
26571690c6c1SJeff Roberson 			if (tdq_idled(tdq) == 0)
26581690c6c1SJeff Roberson 				continue;
26592c27cb3aSAlexander Motin 		}
26601690c6c1SJeff Roberson 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
26612fd4047fSAlexander Motin #else
26622fd4047fSAlexander Motin 		oldswitchcnt = switchcnt;
26632fd4047fSAlexander Motin #endif
26641690c6c1SJeff Roberson 		/*
26651690c6c1SJeff Roberson 		 * If we're switching very frequently, spin while checking
26661690c6c1SJeff Roberson 		 * for load rather than entering a low power state that
26677b55ab05SJeff Roberson 		 * may require an IPI.  However, don't do any busy
26687b55ab05SJeff Roberson 		 * loops while on SMT machines as this simply steals
26697b55ab05SJeff Roberson 		 * cycles from cores doing useful work.
26701690c6c1SJeff Roberson 		 */
267109c8a4ccSJeff Roberson 		if (TDQ_IDLESPIN(tdq) && switchcnt > sched_idlespinthresh) {
26721690c6c1SJeff Roberson 			for (i = 0; i < sched_idlespins; i++) {
26731690c6c1SJeff Roberson 				if (tdq->tdq_load)
26741690c6c1SJeff Roberson 					break;
26751690c6c1SJeff Roberson 				cpu_spinwait();
26761690c6c1SJeff Roberson 			}
26771690c6c1SJeff Roberson 		}
26782c27cb3aSAlexander Motin 
26792c27cb3aSAlexander Motin 		/* If there was context switch during spin, restart it. */
26806c47aaaeSJeff Roberson 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
26812c27cb3aSAlexander Motin 		if (tdq->tdq_load != 0 || switchcnt != oldswitchcnt)
26822c27cb3aSAlexander Motin 			continue;
26832c27cb3aSAlexander Motin 
26842c27cb3aSAlexander Motin 		/* Run main MD idle handler. */
26859f9ad565SAlexander Motin 		tdq->tdq_cpu_idle = 1;
268679654969SAlexander Motin 		/*
268779654969SAlexander Motin 		 * Make sure that tdq_cpu_idle update is globally visible
268879654969SAlexander Motin 		 * before cpu_idle() read tdq_load.  The order is important
268979654969SAlexander Motin 		 * to avoid race with tdq_notify.
269079654969SAlexander Motin 		 */
2691e8677f38SKonstantin Belousov 		atomic_thread_fence_seq_cst();
26922c27cb3aSAlexander Motin 		cpu_idle(switchcnt * 4 > sched_idlespinthresh);
26939f9ad565SAlexander Motin 		tdq->tdq_cpu_idle = 0;
26942c27cb3aSAlexander Motin 
26952c27cb3aSAlexander Motin 		/*
26962c27cb3aSAlexander Motin 		 * Account thread-less hardware interrupts and
26972c27cb3aSAlexander Motin 		 * other wakeup reasons equal to context switches.
26982c27cb3aSAlexander Motin 		 */
26992c27cb3aSAlexander Motin 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
27002c27cb3aSAlexander Motin 		if (switchcnt != oldswitchcnt)
27012c27cb3aSAlexander Motin 			continue;
27022c27cb3aSAlexander Motin 		tdq->tdq_switchcnt++;
27032c27cb3aSAlexander Motin 		oldswitchcnt++;
2704ae7a6b38SJeff Roberson 	}
2705b41f1452SDavid Xu }
2706e7d50326SJeff Roberson 
27077b20fb19SJeff Roberson /*
27087b20fb19SJeff Roberson  * A CPU is entering for the first time or a thread is exiting.
27097b20fb19SJeff Roberson  */
27107b20fb19SJeff Roberson void
27117b20fb19SJeff Roberson sched_throw(struct thread *td)
27127b20fb19SJeff Roberson {
271359c68134SJeff Roberson 	struct thread *newtd;
2714ae7a6b38SJeff Roberson 	struct tdq *tdq;
2715ae7a6b38SJeff Roberson 
2716ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
27177b20fb19SJeff Roberson 	if (td == NULL) {
2718ae7a6b38SJeff Roberson 		/* Correct spinlock nesting and acquire the correct lock. */
2719ae7a6b38SJeff Roberson 		TDQ_LOCK(tdq);
27207b20fb19SJeff Roberson 		spinlock_exit();
27217e3a96eaSJohn Baldwin 		PCPU_SET(switchtime, cpu_ticks());
27227e3a96eaSJohn Baldwin 		PCPU_SET(switchticks, ticks);
27237b20fb19SJeff Roberson 	} else {
2724ae7a6b38SJeff Roberson 		MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
27259727e637SJeff Roberson 		tdq_load_rem(tdq, td);
2726eea4f254SJeff Roberson 		lock_profile_release_lock(&TDQ_LOCKPTR(tdq)->lock_object);
272792de34dfSJohn Baldwin 		td->td_lastcpu = td->td_oncpu;
272892de34dfSJohn Baldwin 		td->td_oncpu = NOCPU;
27297b20fb19SJeff Roberson 	}
27307b20fb19SJeff Roberson 	KASSERT(curthread->td_md.md_spinlock_count == 1, ("invalid count"));
273159c68134SJeff Roberson 	newtd = choosethread();
273259c68134SJeff Roberson 	TDQ_LOCKPTR(tdq)->mtx_lock = (uintptr_t)newtd;
273359c68134SJeff Roberson 	cpu_throw(td, newtd);		/* doesn't return */
27347b20fb19SJeff Roberson }
27357b20fb19SJeff Roberson 
2736ae7a6b38SJeff Roberson /*
2737ae7a6b38SJeff Roberson  * This is called from fork_exit().  Just acquire the correct locks and
2738ae7a6b38SJeff Roberson  * let fork do the rest of the work.
2739ae7a6b38SJeff Roberson  */
27407b20fb19SJeff Roberson void
2741fe54587fSJeff Roberson sched_fork_exit(struct thread *td)
27427b20fb19SJeff Roberson {
2743ae7a6b38SJeff Roberson 	struct tdq *tdq;
2744ae7a6b38SJeff Roberson 	int cpuid;
27457b20fb19SJeff Roberson 
27467b20fb19SJeff Roberson 	/*
27477b20fb19SJeff Roberson 	 * Finish setting up thread glue so that it begins execution in a
2748ae7a6b38SJeff Roberson 	 * non-nested critical section with the scheduler lock held.
27497b20fb19SJeff Roberson 	 */
2750ae7a6b38SJeff Roberson 	cpuid = PCPU_GET(cpuid);
2751ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpuid);
2752ae7a6b38SJeff Roberson 	if (TD_IS_IDLETHREAD(td))
2753ae7a6b38SJeff Roberson 		td->td_lock = TDQ_LOCKPTR(tdq);
2754ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
2755ae7a6b38SJeff Roberson 	td->td_oncpu = cpuid;
275659c68134SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED | MA_NOTRECURSED);
2757eea4f254SJeff Roberson 	lock_profile_obtain_lock_success(
2758eea4f254SJeff Roberson 	    &TDQ_LOCKPTR(tdq)->lock_object, 0, 0, __FILE__, __LINE__);
27597b20fb19SJeff Roberson }
27607b20fb19SJeff Roberson 
27618f51ad55SJeff Roberson /*
27628f51ad55SJeff Roberson  * Create on first use to catch odd startup conditons.
27638f51ad55SJeff Roberson  */
27648f51ad55SJeff Roberson char *
27658f51ad55SJeff Roberson sched_tdname(struct thread *td)
27668f51ad55SJeff Roberson {
27678f51ad55SJeff Roberson #ifdef KTR
27688f51ad55SJeff Roberson 	struct td_sched *ts;
27698f51ad55SJeff Roberson 
277093ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
27718f51ad55SJeff Roberson 	if (ts->ts_name[0] == '\0')
27728f51ad55SJeff Roberson 		snprintf(ts->ts_name, sizeof(ts->ts_name),
27738f51ad55SJeff Roberson 		    "%s tid %d", td->td_name, td->td_tid);
27748f51ad55SJeff Roberson 	return (ts->ts_name);
27758f51ad55SJeff Roberson #else
27768f51ad55SJeff Roberson 	return (td->td_name);
27778f51ad55SJeff Roberson #endif
27788f51ad55SJeff Roberson }
27798f51ad55SJeff Roberson 
278044ad5475SJohn Baldwin #ifdef KTR
278144ad5475SJohn Baldwin void
278244ad5475SJohn Baldwin sched_clear_tdname(struct thread *td)
278344ad5475SJohn Baldwin {
278444ad5475SJohn Baldwin 	struct td_sched *ts;
278544ad5475SJohn Baldwin 
278693ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
278744ad5475SJohn Baldwin 	ts->ts_name[0] = '\0';
278844ad5475SJohn Baldwin }
278944ad5475SJohn Baldwin #endif
279044ad5475SJohn Baldwin 
279107095abfSIvan Voras #ifdef SMP
279207095abfSIvan Voras 
279307095abfSIvan Voras /*
279407095abfSIvan Voras  * Build the CPU topology dump string. Is recursively called to collect
279507095abfSIvan Voras  * the topology tree.
279607095abfSIvan Voras  */
279707095abfSIvan Voras static int
279807095abfSIvan Voras sysctl_kern_sched_topology_spec_internal(struct sbuf *sb, struct cpu_group *cg,
279907095abfSIvan Voras     int indent)
280007095abfSIvan Voras {
280171a19bdcSAttilio Rao 	char cpusetbuf[CPUSETBUFSIZ];
280207095abfSIvan Voras 	int i, first;
280307095abfSIvan Voras 
280407095abfSIvan Voras 	sbuf_printf(sb, "%*s<group level=\"%d\" cache-level=\"%d\">\n", indent,
280519b8a6dbSAndriy Gapon 	    "", 1 + indent / 2, cg->cg_level);
280671a19bdcSAttilio Rao 	sbuf_printf(sb, "%*s <cpu count=\"%d\" mask=\"%s\">", indent, "",
280771a19bdcSAttilio Rao 	    cg->cg_count, cpusetobj_strprint(cpusetbuf, &cg->cg_mask));
280807095abfSIvan Voras 	first = TRUE;
280907095abfSIvan Voras 	for (i = 0; i < MAXCPU; i++) {
281071a19bdcSAttilio Rao 		if (CPU_ISSET(i, &cg->cg_mask)) {
281107095abfSIvan Voras 			if (!first)
281207095abfSIvan Voras 				sbuf_printf(sb, ", ");
281307095abfSIvan Voras 			else
281407095abfSIvan Voras 				first = FALSE;
281507095abfSIvan Voras 			sbuf_printf(sb, "%d", i);
281607095abfSIvan Voras 		}
281707095abfSIvan Voras 	}
281807095abfSIvan Voras 	sbuf_printf(sb, "</cpu>\n");
281907095abfSIvan Voras 
282007095abfSIvan Voras 	if (cg->cg_flags != 0) {
2821611daf7eSIvan Voras 		sbuf_printf(sb, "%*s <flags>", indent, "");
282207095abfSIvan Voras 		if ((cg->cg_flags & CG_FLAG_HTT) != 0)
28235368befbSIvan Voras 			sbuf_printf(sb, "<flag name=\"HTT\">HTT group</flag>");
2824a401f2d0SIvan Voras 		if ((cg->cg_flags & CG_FLAG_THREAD) != 0)
2825a401f2d0SIvan Voras 			sbuf_printf(sb, "<flag name=\"THREAD\">THREAD group</flag>");
28267b55ab05SJeff Roberson 		if ((cg->cg_flags & CG_FLAG_SMT) != 0)
2827a401f2d0SIvan Voras 			sbuf_printf(sb, "<flag name=\"SMT\">SMT group</flag>");
282807095abfSIvan Voras 		sbuf_printf(sb, "</flags>\n");
2829611daf7eSIvan Voras 	}
283007095abfSIvan Voras 
283107095abfSIvan Voras 	if (cg->cg_children > 0) {
283207095abfSIvan Voras 		sbuf_printf(sb, "%*s <children>\n", indent, "");
283307095abfSIvan Voras 		for (i = 0; i < cg->cg_children; i++)
283407095abfSIvan Voras 			sysctl_kern_sched_topology_spec_internal(sb,
283507095abfSIvan Voras 			    &cg->cg_child[i], indent+2);
283607095abfSIvan Voras 		sbuf_printf(sb, "%*s </children>\n", indent, "");
283707095abfSIvan Voras 	}
283807095abfSIvan Voras 	sbuf_printf(sb, "%*s</group>\n", indent, "");
283907095abfSIvan Voras 	return (0);
284007095abfSIvan Voras }
284107095abfSIvan Voras 
284207095abfSIvan Voras /*
284307095abfSIvan Voras  * Sysctl handler for retrieving topology dump. It's a wrapper for
284407095abfSIvan Voras  * the recursive sysctl_kern_smp_topology_spec_internal().
284507095abfSIvan Voras  */
284607095abfSIvan Voras static int
284707095abfSIvan Voras sysctl_kern_sched_topology_spec(SYSCTL_HANDLER_ARGS)
284807095abfSIvan Voras {
284907095abfSIvan Voras 	struct sbuf *topo;
285007095abfSIvan Voras 	int err;
285107095abfSIvan Voras 
285207095abfSIvan Voras 	KASSERT(cpu_top != NULL, ("cpu_top isn't initialized"));
285307095abfSIvan Voras 
2854b97fa22cSIan Lepore 	topo = sbuf_new_for_sysctl(NULL, NULL, 512, req);
285507095abfSIvan Voras 	if (topo == NULL)
285607095abfSIvan Voras 		return (ENOMEM);
285707095abfSIvan Voras 
285807095abfSIvan Voras 	sbuf_printf(topo, "<groups>\n");
285907095abfSIvan Voras 	err = sysctl_kern_sched_topology_spec_internal(topo, cpu_top, 1);
286007095abfSIvan Voras 	sbuf_printf(topo, "</groups>\n");
286107095abfSIvan Voras 
286207095abfSIvan Voras 	if (err == 0) {
2863b97fa22cSIan Lepore 		err = sbuf_finish(topo);
286407095abfSIvan Voras 	}
286507095abfSIvan Voras 	sbuf_delete(topo);
286607095abfSIvan Voras 	return (err);
286707095abfSIvan Voras }
2868b67cc292SDavid Xu 
286907095abfSIvan Voras #endif
287007095abfSIvan Voras 
2871579895dfSAlexander Motin static int
2872579895dfSAlexander Motin sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
2873579895dfSAlexander Motin {
2874579895dfSAlexander Motin 	int error, new_val, period;
2875579895dfSAlexander Motin 
2876579895dfSAlexander Motin 	period = 1000000 / realstathz;
2877579895dfSAlexander Motin 	new_val = period * sched_slice;
2878579895dfSAlexander Motin 	error = sysctl_handle_int(oidp, &new_val, 0, req);
2879579895dfSAlexander Motin 	if (error != 0 || req->newptr == NULL)
2880579895dfSAlexander Motin 		return (error);
2881579895dfSAlexander Motin 	if (new_val <= 0)
2882579895dfSAlexander Motin 		return (EINVAL);
288337f4e025SAlexander Motin 	sched_slice = imax(1, (new_val + period / 2) / period);
28845e5c3873SJeff Roberson 	sched_slice_min = sched_slice / SCHED_SLICE_MIN_DIVISOR;
288537f4e025SAlexander Motin 	hogticks = imax(1, (2 * hz * sched_slice + realstathz / 2) /
288637f4e025SAlexander Motin 	    realstathz);
2887579895dfSAlexander Motin 	return (0);
2888579895dfSAlexander Motin }
2889579895dfSAlexander Motin 
28909727e637SJeff Roberson SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "Scheduler");
2891ae7a6b38SJeff Roberson SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "ULE", 0,
2892e7d50326SJeff Roberson     "Scheduler name");
2893579895dfSAlexander Motin SYSCTL_PROC(_kern_sched, OID_AUTO, quantum, CTLTYPE_INT | CTLFLAG_RW,
2894579895dfSAlexander Motin     NULL, 0, sysctl_kern_quantum, "I",
289537f4e025SAlexander Motin     "Quantum for timeshare threads in microseconds");
2896ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice, CTLFLAG_RW, &sched_slice, 0,
289737f4e025SAlexander Motin     "Quantum for timeshare threads in stathz ticks");
2898ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, interact, CTLFLAG_RW, &sched_interact, 0,
2899ae7a6b38SJeff Roberson     "Interactivity score threshold");
290037f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, preempt_thresh, CTLFLAG_RW,
290137f4e025SAlexander Motin     &preempt_thresh, 0,
290237f4e025SAlexander Motin     "Maximal (lowest) priority for preemption");
290337f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, static_boost, CTLFLAG_RW, &static_boost, 0,
290437f4e025SAlexander Motin     "Assign static kernel priorities to sleeping threads");
290537f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, idlespins, CTLFLAG_RW, &sched_idlespins, 0,
290637f4e025SAlexander Motin     "Number of times idle thread will spin waiting for new work");
290737f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, idlespinthresh, CTLFLAG_RW,
290837f4e025SAlexander Motin     &sched_idlespinthresh, 0,
290937f4e025SAlexander Motin     "Threshold before we will permit idle thread spinning");
29107b8bfa0dSJeff Roberson #ifdef SMP
2911ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, affinity, CTLFLAG_RW, &affinity, 0,
2912ae7a6b38SJeff Roberson     "Number of hz ticks to keep thread affinity for");
2913ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, balance, CTLFLAG_RW, &rebalance, 0,
2914ae7a6b38SJeff Roberson     "Enables the long-term load balancer");
29157fcf154aSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, balance_interval, CTLFLAG_RW,
29167fcf154aSJeff Roberson     &balance_interval, 0,
2917579895dfSAlexander Motin     "Average period in stathz ticks to run the long-term balancer");
2918ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, steal_idle, CTLFLAG_RW, &steal_idle, 0,
2919ae7a6b38SJeff Roberson     "Attempts to steal work from other cores before idling");
292028994a58SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, steal_thresh, CTLFLAG_RW, &steal_thresh, 0,
292137f4e025SAlexander Motin     "Minimum load on remote CPU before we'll steal");
292207095abfSIvan Voras SYSCTL_PROC(_kern_sched, OID_AUTO, topology_spec, CTLTYPE_STRING |
292307095abfSIvan Voras     CTLFLAG_RD, NULL, 0, sysctl_kern_sched_topology_spec, "A",
292407095abfSIvan Voras     "XML dump of detected CPU topology");
29257b8bfa0dSJeff Roberson #endif
2926e7d50326SJeff Roberson 
292754b0e65fSJeff Roberson /* ps compat.  All cpu percentages from ULE are weighted. */
2928a5423ea3SJeff Roberson static int ccpu = 0;
2929e7d50326SJeff Roberson SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
2930