xref: /freebsd/sys/kern/sched_ule.c (revision 8bb173fb5bc33a02d5a4670c9a60bba0ece07bac)
135e6168fSJeff Roberson /*-
28a36da99SPedro F. Giffuni  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
38a36da99SPedro F. Giffuni  *
4e7d50326SJeff Roberson  * Copyright (c) 2002-2007, Jeffrey Roberson <jeff@freebsd.org>
535e6168fSJeff Roberson  * All rights reserved.
635e6168fSJeff Roberson  *
735e6168fSJeff Roberson  * Redistribution and use in source and binary forms, with or without
835e6168fSJeff Roberson  * modification, are permitted provided that the following conditions
935e6168fSJeff Roberson  * are met:
1035e6168fSJeff Roberson  * 1. Redistributions of source code must retain the above copyright
1135e6168fSJeff Roberson  *    notice unmodified, this list of conditions, and the following
1235e6168fSJeff Roberson  *    disclaimer.
1335e6168fSJeff Roberson  * 2. Redistributions in binary form must reproduce the above copyright
1435e6168fSJeff Roberson  *    notice, this list of conditions and the following disclaimer in the
1535e6168fSJeff Roberson  *    documentation and/or other materials provided with the distribution.
1635e6168fSJeff Roberson  *
1735e6168fSJeff Roberson  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1835e6168fSJeff Roberson  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1935e6168fSJeff Roberson  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
2035e6168fSJeff Roberson  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
2135e6168fSJeff Roberson  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
2235e6168fSJeff Roberson  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2335e6168fSJeff Roberson  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2435e6168fSJeff Roberson  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2535e6168fSJeff Roberson  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
2635e6168fSJeff Roberson  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2735e6168fSJeff Roberson  */
2835e6168fSJeff Roberson 
29ae7a6b38SJeff Roberson /*
30ae7a6b38SJeff Roberson  * This file implements the ULE scheduler.  ULE supports independent CPU
31ae7a6b38SJeff Roberson  * run queues and fine grain locking.  It has superior interactive
32ae7a6b38SJeff Roberson  * performance under load even on uni-processor systems.
33ae7a6b38SJeff Roberson  *
34ae7a6b38SJeff Roberson  * etymology:
35a5423ea3SJeff Roberson  *   ULE is the last three letters in schedule.  It owes its name to a
36ae7a6b38SJeff Roberson  * generic user created for a scheduling system by Paul Mikesell at
37ae7a6b38SJeff Roberson  * Isilon Systems and a general lack of creativity on the part of the author.
38ae7a6b38SJeff Roberson  */
39ae7a6b38SJeff Roberson 
40677b542eSDavid E. O'Brien #include <sys/cdefs.h>
41113dda8aSJeff Roberson __FBSDID("$FreeBSD$");
42677b542eSDavid E. O'Brien 
434da0d332SPeter Wemm #include "opt_hwpmc_hooks.h"
444da0d332SPeter Wemm #include "opt_sched.h"
459923b511SScott Long 
4635e6168fSJeff Roberson #include <sys/param.h>
4735e6168fSJeff Roberson #include <sys/systm.h>
482c3490b1SMarcel Moolenaar #include <sys/kdb.h>
4935e6168fSJeff Roberson #include <sys/kernel.h>
5035e6168fSJeff Roberson #include <sys/ktr.h>
51c149e542SAttilio Rao #include <sys/limits.h>
5235e6168fSJeff Roberson #include <sys/lock.h>
5335e6168fSJeff Roberson #include <sys/mutex.h>
5435e6168fSJeff Roberson #include <sys/proc.h>
55245f3abfSJeff Roberson #include <sys/resource.h>
569bacd788SJeff Roberson #include <sys/resourcevar.h>
5735e6168fSJeff Roberson #include <sys/sched.h>
58b3e9e682SRyan Stone #include <sys/sdt.h>
5935e6168fSJeff Roberson #include <sys/smp.h>
6035e6168fSJeff Roberson #include <sys/sx.h>
6135e6168fSJeff Roberson #include <sys/sysctl.h>
6235e6168fSJeff Roberson #include <sys/sysproto.h>
63f5c157d9SJohn Baldwin #include <sys/turnstile.h>
64af29f399SDmitry Chagin #include <sys/umtxvar.h>
6535e6168fSJeff Roberson #include <sys/vmmeter.h>
6662fa74d9SJeff Roberson #include <sys/cpuset.h>
6707095abfSIvan Voras #include <sys/sbuf.h>
6835e6168fSJeff Roberson 
69ebccf1e3SJoseph Koshy #ifdef HWPMC_HOOKS
70ebccf1e3SJoseph Koshy #include <sys/pmckern.h>
71ebccf1e3SJoseph Koshy #endif
72ebccf1e3SJoseph Koshy 
736f5f25e5SJohn Birrell #ifdef KDTRACE_HOOKS
746f5f25e5SJohn Birrell #include <sys/dtrace_bsd.h>
7561322a0aSAlexander Motin int __read_mostly		dtrace_vtime_active;
766f5f25e5SJohn Birrell dtrace_vtime_switch_func_t	dtrace_vtime_switch_func;
776f5f25e5SJohn Birrell #endif
786f5f25e5SJohn Birrell 
7935e6168fSJeff Roberson #include <machine/cpu.h>
8022bf7d9aSJeff Roberson #include <machine/smp.h>
8135e6168fSJeff Roberson 
82ae7a6b38SJeff Roberson #define	KTR_ULE	0
8314618990SJeff Roberson 
840d2cf837SJeff Roberson #define	TS_NAME_LEN (MAXCOMLEN + sizeof(" td ") + sizeof(__XSTRING(UINT_MAX)))
850d2cf837SJeff Roberson #define	TDQ_NAME_LEN	(sizeof("sched lock ") + sizeof(__XSTRING(MAXCPU)))
866338c579SAttilio Rao #define	TDQ_LOADNAME_LEN	(sizeof("CPU ") + sizeof(__XSTRING(MAXCPU)) - 1 + sizeof(" load"))
878f51ad55SJeff Roberson 
886b2f763fSJeff Roberson /*
89ae7a6b38SJeff Roberson  * Thread scheduler specific section.  All fields are protected
90ae7a6b38SJeff Roberson  * by the thread lock.
91ed062c8dSJulian Elischer  */
92ad1e7d28SJulian Elischer struct td_sched {
93ae7a6b38SJeff Roberson 	struct runq	*ts_runq;	/* Run-queue we're queued on. */
94ae7a6b38SJeff Roberson 	short		ts_flags;	/* TSF_* flags. */
95e77f9fedSAdrian Chadd 	int		ts_cpu;		/* CPU that we have affinity for. */
9673daf66fSJeff Roberson 	int		ts_rltick;	/* Real last tick, for affinity. */
97ae7a6b38SJeff Roberson 	int		ts_slice;	/* Ticks of slice remaining. */
98ae7a6b38SJeff Roberson 	u_int		ts_slptime;	/* Number of ticks we vol. slept */
99ae7a6b38SJeff Roberson 	u_int		ts_runtime;	/* Number of ticks we were running */
100ad1e7d28SJulian Elischer 	int		ts_ltick;	/* Last tick that we were running on */
101ad1e7d28SJulian Elischer 	int		ts_ftick;	/* First tick that we were running on */
102ad1e7d28SJulian Elischer 	int		ts_ticks;	/* Tick count */
1038f51ad55SJeff Roberson #ifdef KTR
1048f51ad55SJeff Roberson 	char		ts_name[TS_NAME_LEN];
1058f51ad55SJeff Roberson #endif
106ed062c8dSJulian Elischer };
107ad1e7d28SJulian Elischer /* flags kept in ts_flags */
1087b8bfa0dSJeff Roberson #define	TSF_BOUND	0x0001		/* Thread can not migrate. */
1097b8bfa0dSJeff Roberson #define	TSF_XFERABLE	0x0002		/* Thread was added as transferable. */
11035e6168fSJeff Roberson 
11162fa74d9SJeff Roberson #define	THREAD_CAN_MIGRATE(td)	((td)->td_pinned == 0)
11262fa74d9SJeff Roberson #define	THREAD_CAN_SCHED(td, cpu)	\
11362fa74d9SJeff Roberson     CPU_ISSET((cpu), &(td)->td_cpuset->cs_mask)
11462fa74d9SJeff Roberson 
11593ccd6bfSKonstantin Belousov _Static_assert(sizeof(struct thread) + sizeof(struct td_sched) <=
11693ccd6bfSKonstantin Belousov     sizeof(struct thread0_storage),
11793ccd6bfSKonstantin Belousov     "increase struct thread0_storage.t0st_sched size");
11893ccd6bfSKonstantin Belousov 
11935e6168fSJeff Roberson /*
12012d56c0fSJohn Baldwin  * Priority ranges used for interactive and non-interactive timeshare
1212dc29adbSJohn Baldwin  * threads.  The timeshare priorities are split up into four ranges.
1222dc29adbSJohn Baldwin  * The first range handles interactive threads.  The last three ranges
1232dc29adbSJohn Baldwin  * (NHALF, x, and NHALF) handle non-interactive threads with the outer
1242dc29adbSJohn Baldwin  * ranges supporting nice values.
12512d56c0fSJohn Baldwin  */
1262dc29adbSJohn Baldwin #define	PRI_TIMESHARE_RANGE	(PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
1272dc29adbSJohn Baldwin #define	PRI_INTERACT_RANGE	((PRI_TIMESHARE_RANGE - SCHED_PRI_NRESV) / 2)
12816705791SAndriy Gapon #define	PRI_BATCH_RANGE		(PRI_TIMESHARE_RANGE - PRI_INTERACT_RANGE)
1292dc29adbSJohn Baldwin 
1302dc29adbSJohn Baldwin #define	PRI_MIN_INTERACT	PRI_MIN_TIMESHARE
1312dc29adbSJohn Baldwin #define	PRI_MAX_INTERACT	(PRI_MIN_TIMESHARE + PRI_INTERACT_RANGE - 1)
1322dc29adbSJohn Baldwin #define	PRI_MIN_BATCH		(PRI_MIN_TIMESHARE + PRI_INTERACT_RANGE)
13312d56c0fSJohn Baldwin #define	PRI_MAX_BATCH		PRI_MAX_TIMESHARE
13412d56c0fSJohn Baldwin 
13512d56c0fSJohn Baldwin /*
136e7d50326SJeff Roberson  * Cpu percentage computation macros and defines.
137e1f89c22SJeff Roberson  *
138e7d50326SJeff Roberson  * SCHED_TICK_SECS:	Number of seconds to average the cpu usage across.
139e7d50326SJeff Roberson  * SCHED_TICK_TARG:	Number of hz ticks to average the cpu usage across.
1408ab80cf0SJeff Roberson  * SCHED_TICK_MAX:	Maximum number of ticks before scaling back.
141e7d50326SJeff Roberson  * SCHED_TICK_SHIFT:	Shift factor to avoid rounding away results.
142e7d50326SJeff Roberson  * SCHED_TICK_HZ:	Compute the number of hz ticks for a given ticks count.
143e7d50326SJeff Roberson  * SCHED_TICK_TOTAL:	Gives the amount of time we've been recording ticks.
14435e6168fSJeff Roberson  */
145e7d50326SJeff Roberson #define	SCHED_TICK_SECS		10
146e7d50326SJeff Roberson #define	SCHED_TICK_TARG		(hz * SCHED_TICK_SECS)
1478ab80cf0SJeff Roberson #define	SCHED_TICK_MAX		(SCHED_TICK_TARG + hz)
148e7d50326SJeff Roberson #define	SCHED_TICK_SHIFT	10
149e7d50326SJeff Roberson #define	SCHED_TICK_HZ(ts)	((ts)->ts_ticks >> SCHED_TICK_SHIFT)
150eddb4efaSJeff Roberson #define	SCHED_TICK_TOTAL(ts)	(max((ts)->ts_ltick - (ts)->ts_ftick, hz))
15135e6168fSJeff Roberson 
15235e6168fSJeff Roberson /*
153e7d50326SJeff Roberson  * These macros determine priorities for non-interactive threads.  They are
154e7d50326SJeff Roberson  * assigned a priority based on their recent cpu utilization as expressed
155e7d50326SJeff Roberson  * by the ratio of ticks to the tick total.  NHALF priorities at the start
156e7d50326SJeff Roberson  * and end of the MIN to MAX timeshare range are only reachable with negative
157e7d50326SJeff Roberson  * or positive nice respectively.
158e7d50326SJeff Roberson  *
159e7d50326SJeff Roberson  * PRI_RANGE:	Priority range for utilization dependent priorities.
160e7d50326SJeff Roberson  * PRI_NRESV:	Number of nice values.
161e7d50326SJeff Roberson  * PRI_TICKS:	Compute a priority in PRI_RANGE from the ticks count and total.
162e7d50326SJeff Roberson  * PRI_NICE:	Determines the part of the priority inherited from nice.
163e7d50326SJeff Roberson  */
164e7d50326SJeff Roberson #define	SCHED_PRI_NRESV		(PRIO_MAX - PRIO_MIN)
165e7d50326SJeff Roberson #define	SCHED_PRI_NHALF		(SCHED_PRI_NRESV / 2)
16612d56c0fSJohn Baldwin #define	SCHED_PRI_MIN		(PRI_MIN_BATCH + SCHED_PRI_NHALF)
16712d56c0fSJohn Baldwin #define	SCHED_PRI_MAX		(PRI_MAX_BATCH - SCHED_PRI_NHALF)
16878920008SJohn Baldwin #define	SCHED_PRI_RANGE		(SCHED_PRI_MAX - SCHED_PRI_MIN + 1)
169e7d50326SJeff Roberson #define	SCHED_PRI_TICKS(ts)						\
170e7d50326SJeff Roberson     (SCHED_TICK_HZ((ts)) /						\
1711e516cf5SJeff Roberson     (roundup(SCHED_TICK_TOTAL((ts)), SCHED_PRI_RANGE) / SCHED_PRI_RANGE))
172e7d50326SJeff Roberson #define	SCHED_PRI_NICE(nice)	(nice)
173e7d50326SJeff Roberson 
174e7d50326SJeff Roberson /*
175e7d50326SJeff Roberson  * These determine the interactivity of a process.  Interactivity differs from
176e7d50326SJeff Roberson  * cpu utilization in that it expresses the voluntary time slept vs time ran
177e7d50326SJeff Roberson  * while cpu utilization includes all time not running.  This more accurately
178e7d50326SJeff Roberson  * models the intent of the thread.
17935e6168fSJeff Roberson  *
180407b0157SJeff Roberson  * SLP_RUN_MAX:	Maximum amount of sleep time + run time we'll accumulate
181407b0157SJeff Roberson  *		before throttling back.
182d322132cSJeff Roberson  * SLP_RUN_FORK:	Maximum slp+run time to inherit at fork time.
183210491d3SJeff Roberson  * INTERACT_MAX:	Maximum interactivity value.  Smaller is better.
1849f518f20SAttilio Rao  * INTERACT_THRESH:	Threshold for placement on the current runq.
18535e6168fSJeff Roberson  */
186e7d50326SJeff Roberson #define	SCHED_SLP_RUN_MAX	((hz * 5) << SCHED_TICK_SHIFT)
187e7d50326SJeff Roberson #define	SCHED_SLP_RUN_FORK	((hz / 2) << SCHED_TICK_SHIFT)
188210491d3SJeff Roberson #define	SCHED_INTERACT_MAX	(100)
189210491d3SJeff Roberson #define	SCHED_INTERACT_HALF	(SCHED_INTERACT_MAX / 2)
1904c9612c6SJeff Roberson #define	SCHED_INTERACT_THRESH	(30)
191e1f89c22SJeff Roberson 
1925e5c3873SJeff Roberson /*
1935e5c3873SJeff Roberson  * These parameters determine the slice behavior for batch work.
1945e5c3873SJeff Roberson  */
1955e5c3873SJeff Roberson #define	SCHED_SLICE_DEFAULT_DIVISOR	10	/* ~94 ms, 12 stathz ticks. */
1965e5c3873SJeff Roberson #define	SCHED_SLICE_MIN_DIVISOR		6	/* DEFAULT/MIN = ~16 ms. */
1975e5c3873SJeff Roberson 
1983d7f4117SAlexander Motin /* Flags kept in td_flags. */
1993d7f4117SAlexander Motin #define	TDF_SLICEEND	TDF_SCHED2	/* Thread time slice is over. */
2003d7f4117SAlexander Motin 
20135e6168fSJeff Roberson /*
202e7d50326SJeff Roberson  * tickincr:		Converts a stathz tick into a hz domain scaled by
203e7d50326SJeff Roberson  *			the shift factor.  Without the shift the error rate
204e7d50326SJeff Roberson  *			due to rounding would be unacceptably high.
205e7d50326SJeff Roberson  * realstathz:		stathz is sometimes 0 and run off of hz.
206e7d50326SJeff Roberson  * sched_slice:		Runtime of each thread before rescheduling.
207ae7a6b38SJeff Roberson  * preempt_thresh:	Priority threshold for preemption and remote IPIs.
20835e6168fSJeff Roberson  */
20961322a0aSAlexander Motin static int __read_mostly sched_interact = SCHED_INTERACT_THRESH;
21061322a0aSAlexander Motin static int __read_mostly tickincr = 8 << SCHED_TICK_SHIFT;
21161322a0aSAlexander Motin static int __read_mostly realstathz = 127;	/* reset during boot. */
21261322a0aSAlexander Motin static int __read_mostly sched_slice = 10;	/* reset during boot. */
21361322a0aSAlexander Motin static int __read_mostly sched_slice_min = 1;	/* reset during boot. */
21402e2d6b4SJeff Roberson #ifdef PREEMPTION
21502e2d6b4SJeff Roberson #ifdef FULL_PREEMPTION
21661322a0aSAlexander Motin static int __read_mostly preempt_thresh = PRI_MAX_IDLE;
21702e2d6b4SJeff Roberson #else
21861322a0aSAlexander Motin static int __read_mostly preempt_thresh = PRI_MIN_KERN;
21902e2d6b4SJeff Roberson #endif
22002e2d6b4SJeff Roberson #else
22161322a0aSAlexander Motin static int __read_mostly preempt_thresh = 0;
22202e2d6b4SJeff Roberson #endif
22361322a0aSAlexander Motin static int __read_mostly static_boost = PRI_MIN_BATCH;
22461322a0aSAlexander Motin static int __read_mostly sched_idlespins = 10000;
22561322a0aSAlexander Motin static int __read_mostly sched_idlespinthresh = -1;
226ae7a6b38SJeff Roberson 
22735e6168fSJeff Roberson /*
228ae7a6b38SJeff Roberson  * tdq - per processor runqs and statistics.  All fields are protected by the
229ae7a6b38SJeff Roberson  * tdq_lock.  The load and lowpri may be accessed without to avoid excess
230ae7a6b38SJeff Roberson  * locking in sched_pickcpu();
23135e6168fSJeff Roberson  */
232ad1e7d28SJulian Elischer struct tdq {
23339f819e2SJim Harris 	/*
23439f819e2SJim Harris 	 * Ordered to improve efficiency of cpu_search() and switch().
23539f819e2SJim Harris 	 * tdq_lock is padded to avoid false sharing with tdq_load and
23639f819e2SJim Harris 	 * tdq_cpu_idle.
23739f819e2SJim Harris 	 */
2384ceaf45dSAttilio Rao 	struct mtx_padalign tdq_lock;		/* run queue lock. */
23973daf66fSJeff Roberson 	struct cpu_group *tdq_cg;		/* Pointer to cpu topology. */
2401690c6c1SJeff Roberson 	volatile int	tdq_load;		/* Aggregate load. */
2419f9ad565SAlexander Motin 	volatile int	tdq_cpu_idle;		/* cpu_idle() is active. */
24273daf66fSJeff Roberson 	int		tdq_sysload;		/* For loadavg, !ITHD load. */
24397e9382dSDon Lewis 	volatile int	tdq_transferable;	/* Transferable thread count. */
24497e9382dSDon Lewis 	volatile short	tdq_switchcnt;		/* Switches this tick. */
24597e9382dSDon Lewis 	volatile short	tdq_oldswitchcnt;	/* Switches last tick. */
24673daf66fSJeff Roberson 	u_char		tdq_lowpri;		/* Lowest priority thread. */
2477789ab32SMark Johnston 	u_char		tdq_owepreempt;		/* Remote preemption pending. */
24873daf66fSJeff Roberson 	u_char		tdq_idx;		/* Current insert index. */
24973daf66fSJeff Roberson 	u_char		tdq_ridx;		/* Current removal index. */
250018ff686SJeff Roberson 	int		tdq_id;			/* cpuid. */
251e7d50326SJeff Roberson 	struct runq	tdq_realtime;		/* real-time run queue. */
252ae7a6b38SJeff Roberson 	struct runq	tdq_timeshare;		/* timeshare run queue. */
253ae7a6b38SJeff Roberson 	struct runq	tdq_idle;		/* Queue of IDLE threads. */
2548f51ad55SJeff Roberson 	char		tdq_name[TDQ_NAME_LEN];
2558f51ad55SJeff Roberson #ifdef KTR
2568f51ad55SJeff Roberson 	char		tdq_loadname[TDQ_LOADNAME_LEN];
2578f51ad55SJeff Roberson #endif
258ae7a6b38SJeff Roberson } __aligned(64);
25935e6168fSJeff Roberson 
2601690c6c1SJeff Roberson /* Idle thread states and config. */
2611690c6c1SJeff Roberson #define	TDQ_RUNNING	1
2621690c6c1SJeff Roberson #define	TDQ_IDLE	2
2637b8bfa0dSJeff Roberson 
26480f86c9fSJeff Roberson #ifdef SMP
26561322a0aSAlexander Motin struct cpu_group __read_mostly *cpu_top;		/* CPU topology */
2667b8bfa0dSJeff Roberson 
26762fa74d9SJeff Roberson #define	SCHED_AFFINITY_DEFAULT	(max(1, hz / 1000))
26862fa74d9SJeff Roberson #define	SCHED_AFFINITY(ts, t)	((ts)->ts_rltick > ticks - ((t) * affinity))
2697b8bfa0dSJeff Roberson 
2707b8bfa0dSJeff Roberson /*
2717b8bfa0dSJeff Roberson  * Run-time tunables.
2727b8bfa0dSJeff Roberson  */
27328994a58SJeff Roberson static int rebalance = 1;
2747fcf154aSJeff Roberson static int balance_interval = 128;	/* Default set in sched_initticks(). */
27561322a0aSAlexander Motin static int __read_mostly affinity;
27661322a0aSAlexander Motin static int __read_mostly steal_idle = 1;
27761322a0aSAlexander Motin static int __read_mostly steal_thresh = 2;
27861322a0aSAlexander Motin static int __read_mostly always_steal = 0;
27961322a0aSAlexander Motin static int __read_mostly trysteal_limit = 2;
28080f86c9fSJeff Roberson 
28135e6168fSJeff Roberson /*
282d2ad694cSJeff Roberson  * One thread queue per processor.
28335e6168fSJeff Roberson  */
28461322a0aSAlexander Motin static struct tdq __read_mostly *balance_tdq;
2857fcf154aSJeff Roberson static int balance_ticks;
286018ff686SJeff Roberson DPCPU_DEFINE_STATIC(struct tdq, tdq);
2872bf95012SAndrew Turner DPCPU_DEFINE_STATIC(uint32_t, randomval);
288dc03363dSJeff Roberson 
289018ff686SJeff Roberson #define	TDQ_SELF()	((struct tdq *)PCPU_GET(sched))
290018ff686SJeff Roberson #define	TDQ_CPU(x)	(DPCPU_ID_PTR((x), tdq))
291018ff686SJeff Roberson #define	TDQ_ID(x)	((x)->tdq_id)
29280f86c9fSJeff Roberson #else	/* !SMP */
293ad1e7d28SJulian Elischer static struct tdq	tdq_cpu;
294dc03363dSJeff Roberson 
29536b36916SJeff Roberson #define	TDQ_ID(x)	(0)
296ad1e7d28SJulian Elischer #define	TDQ_SELF()	(&tdq_cpu)
297ad1e7d28SJulian Elischer #define	TDQ_CPU(x)	(&tdq_cpu)
2980a016a05SJeff Roberson #endif
29935e6168fSJeff Roberson 
300ae7a6b38SJeff Roberson #define	TDQ_LOCK_ASSERT(t, type)	mtx_assert(TDQ_LOCKPTR((t)), (type))
301ae7a6b38SJeff Roberson #define	TDQ_LOCK(t)		mtx_lock_spin(TDQ_LOCKPTR((t)))
302ae7a6b38SJeff Roberson #define	TDQ_LOCK_FLAGS(t, f)	mtx_lock_spin_flags(TDQ_LOCKPTR((t)), (f))
303*8bb173fbSAlexander Motin #define	TDQ_TRYLOCK(t)		mtx_trylock_spin(TDQ_LOCKPTR((t)))
304*8bb173fbSAlexander Motin #define	TDQ_TRYLOCK_FLAGS(t, f)	mtx_trylock_spin_flags(TDQ_LOCKPTR((t)), (f))
305ae7a6b38SJeff Roberson #define	TDQ_UNLOCK(t)		mtx_unlock_spin(TDQ_LOCKPTR((t)))
3064ceaf45dSAttilio Rao #define	TDQ_LOCKPTR(t)		((struct mtx *)(&(t)->tdq_lock))
307ae7a6b38SJeff Roberson 
3088460a577SJohn Birrell static void sched_priority(struct thread *);
30921381d1bSJeff Roberson static void sched_thread_priority(struct thread *, u_char);
3108460a577SJohn Birrell static int sched_interact_score(struct thread *);
3118460a577SJohn Birrell static void sched_interact_update(struct thread *);
3128460a577SJohn Birrell static void sched_interact_fork(struct thread *);
3137295465eSAlexander Motin static void sched_pctcpu_update(struct td_sched *, int);
31435e6168fSJeff Roberson 
3155d7ef00cSJeff Roberson /* Operations on per processor queues */
3169727e637SJeff Roberson static struct thread *tdq_choose(struct tdq *);
317018ff686SJeff Roberson static void tdq_setup(struct tdq *, int i);
3189727e637SJeff Roberson static void tdq_load_add(struct tdq *, struct thread *);
3199727e637SJeff Roberson static void tdq_load_rem(struct tdq *, struct thread *);
3209727e637SJeff Roberson static __inline void tdq_runq_add(struct tdq *, struct thread *, int);
3219727e637SJeff Roberson static __inline void tdq_runq_rem(struct tdq *, struct thread *);
322ff256d9cSJeff Roberson static inline int sched_shouldpreempt(int, int, int);
323ad1e7d28SJulian Elischer void tdq_print(int cpu);
324e7d50326SJeff Roberson static void runq_print(struct runq *rq);
325ae7a6b38SJeff Roberson static void tdq_add(struct tdq *, struct thread *, int);
3265d7ef00cSJeff Roberson #ifdef SMP
32797e9382dSDon Lewis static struct thread *tdq_move(struct tdq *, struct tdq *);
328ad1e7d28SJulian Elischer static int tdq_idled(struct tdq *);
32927ee18adSRyan Stone static void tdq_notify(struct tdq *, struct thread *);
3309727e637SJeff Roberson static struct thread *tdq_steal(struct tdq *, int);
3319727e637SJeff Roberson static struct thread *runq_steal(struct runq *, int);
3329727e637SJeff Roberson static int sched_pickcpu(struct thread *, int);
3337fcf154aSJeff Roberson static void sched_balance(void);
33462fa74d9SJeff Roberson static int sched_balance_pair(struct tdq *, struct tdq *);
3359727e637SJeff Roberson static inline struct tdq *sched_setcpu(struct thread *, int, int);
336ae7a6b38SJeff Roberson static inline void thread_unblock_switch(struct thread *, struct mtx *);
33707095abfSIvan Voras static int sysctl_kern_sched_topology_spec(SYSCTL_HANDLER_ARGS);
33807095abfSIvan Voras static int sysctl_kern_sched_topology_spec_internal(struct sbuf *sb,
33907095abfSIvan Voras     struct cpu_group *cg, int indent);
3405d7ef00cSJeff Roberson #endif
3415d7ef00cSJeff Roberson 
342e7d50326SJeff Roberson static void sched_setup(void *dummy);
343237fdd78SRobert Watson SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL);
344e7d50326SJeff Roberson 
345e7d50326SJeff Roberson static void sched_initticks(void *dummy);
346237fdd78SRobert Watson SYSINIT(sched_initticks, SI_SUB_CLOCKS, SI_ORDER_THIRD, sched_initticks,
347237fdd78SRobert Watson     NULL);
348e7d50326SJeff Roberson 
349b3e9e682SRyan Stone SDT_PROVIDER_DEFINE(sched);
350b3e9e682SRyan Stone 
351d9fae5abSAndriy Gapon SDT_PROBE_DEFINE3(sched, , , change__pri, "struct thread *",
352b3e9e682SRyan Stone     "struct proc *", "uint8_t");
353d9fae5abSAndriy Gapon SDT_PROBE_DEFINE3(sched, , , dequeue, "struct thread *",
354b3e9e682SRyan Stone     "struct proc *", "void *");
355d9fae5abSAndriy Gapon SDT_PROBE_DEFINE4(sched, , , enqueue, "struct thread *",
356b3e9e682SRyan Stone     "struct proc *", "void *", "int");
357d9fae5abSAndriy Gapon SDT_PROBE_DEFINE4(sched, , , lend__pri, "struct thread *",
358b3e9e682SRyan Stone     "struct proc *", "uint8_t", "struct thread *");
359d9fae5abSAndriy Gapon SDT_PROBE_DEFINE2(sched, , , load__change, "int", "int");
360d9fae5abSAndriy Gapon SDT_PROBE_DEFINE2(sched, , , off__cpu, "struct thread *",
361b3e9e682SRyan Stone     "struct proc *");
362d9fae5abSAndriy Gapon SDT_PROBE_DEFINE(sched, , , on__cpu);
363d9fae5abSAndriy Gapon SDT_PROBE_DEFINE(sched, , , remain__cpu);
364d9fae5abSAndriy Gapon SDT_PROBE_DEFINE2(sched, , , surrender, "struct thread *",
365b3e9e682SRyan Stone     "struct proc *");
366b3e9e682SRyan Stone 
3670567b6ccSWarner Losh /*
368ae7a6b38SJeff Roberson  * Print the threads waiting on a run-queue.
369ae7a6b38SJeff Roberson  */
370e7d50326SJeff Roberson static void
371e7d50326SJeff Roberson runq_print(struct runq *rq)
372e7d50326SJeff Roberson {
373e7d50326SJeff Roberson 	struct rqhead *rqh;
3749727e637SJeff Roberson 	struct thread *td;
375e7d50326SJeff Roberson 	int pri;
376e7d50326SJeff Roberson 	int j;
377e7d50326SJeff Roberson 	int i;
378e7d50326SJeff Roberson 
379e7d50326SJeff Roberson 	for (i = 0; i < RQB_LEN; i++) {
380e7d50326SJeff Roberson 		printf("\t\trunq bits %d 0x%zx\n",
381e7d50326SJeff Roberson 		    i, rq->rq_status.rqb_bits[i]);
382e7d50326SJeff Roberson 		for (j = 0; j < RQB_BPW; j++)
383e7d50326SJeff Roberson 			if (rq->rq_status.rqb_bits[i] & (1ul << j)) {
384e7d50326SJeff Roberson 				pri = j + (i << RQB_L2BPW);
385e7d50326SJeff Roberson 				rqh = &rq->rq_queues[pri];
3869727e637SJeff Roberson 				TAILQ_FOREACH(td, rqh, td_runq) {
387e7d50326SJeff Roberson 					printf("\t\t\ttd %p(%s) priority %d rqindex %d pri %d\n",
3889727e637SJeff Roberson 					    td, td->td_name, td->td_priority,
3899727e637SJeff Roberson 					    td->td_rqindex, pri);
390e7d50326SJeff Roberson 				}
391e7d50326SJeff Roberson 			}
392e7d50326SJeff Roberson 	}
393e7d50326SJeff Roberson }
394e7d50326SJeff Roberson 
395ae7a6b38SJeff Roberson /*
396ae7a6b38SJeff Roberson  * Print the status of a per-cpu thread queue.  Should be a ddb show cmd.
397ae7a6b38SJeff Roberson  */
39815dc847eSJeff Roberson void
399ad1e7d28SJulian Elischer tdq_print(int cpu)
40015dc847eSJeff Roberson {
401ad1e7d28SJulian Elischer 	struct tdq *tdq;
40215dc847eSJeff Roberson 
403ad1e7d28SJulian Elischer 	tdq = TDQ_CPU(cpu);
40415dc847eSJeff Roberson 
405c47f202bSJeff Roberson 	printf("tdq %d:\n", TDQ_ID(tdq));
40662fa74d9SJeff Roberson 	printf("\tlock            %p\n", TDQ_LOCKPTR(tdq));
40762fa74d9SJeff Roberson 	printf("\tLock name:      %s\n", tdq->tdq_name);
408d2ad694cSJeff Roberson 	printf("\tload:           %d\n", tdq->tdq_load);
4091690c6c1SJeff Roberson 	printf("\tswitch cnt:     %d\n", tdq->tdq_switchcnt);
4101690c6c1SJeff Roberson 	printf("\told switch cnt: %d\n", tdq->tdq_oldswitchcnt);
411e7d50326SJeff Roberson 	printf("\ttimeshare idx:  %d\n", tdq->tdq_idx);
4123f872f85SJeff Roberson 	printf("\ttimeshare ridx: %d\n", tdq->tdq_ridx);
4131690c6c1SJeff Roberson 	printf("\tload transferable: %d\n", tdq->tdq_transferable);
4141690c6c1SJeff Roberson 	printf("\tlowest priority:   %d\n", tdq->tdq_lowpri);
415e7d50326SJeff Roberson 	printf("\trealtime runq:\n");
416e7d50326SJeff Roberson 	runq_print(&tdq->tdq_realtime);
417e7d50326SJeff Roberson 	printf("\ttimeshare runq:\n");
418e7d50326SJeff Roberson 	runq_print(&tdq->tdq_timeshare);
419e7d50326SJeff Roberson 	printf("\tidle runq:\n");
420e7d50326SJeff Roberson 	runq_print(&tdq->tdq_idle);
42115dc847eSJeff Roberson }
42215dc847eSJeff Roberson 
423ff256d9cSJeff Roberson static inline int
424ff256d9cSJeff Roberson sched_shouldpreempt(int pri, int cpri, int remote)
425ff256d9cSJeff Roberson {
426ff256d9cSJeff Roberson 	/*
427ff256d9cSJeff Roberson 	 * If the new priority is not better than the current priority there is
428ff256d9cSJeff Roberson 	 * nothing to do.
429ff256d9cSJeff Roberson 	 */
430ff256d9cSJeff Roberson 	if (pri >= cpri)
431ff256d9cSJeff Roberson 		return (0);
432ff256d9cSJeff Roberson 	/*
433ff256d9cSJeff Roberson 	 * Always preempt idle.
434ff256d9cSJeff Roberson 	 */
435ff256d9cSJeff Roberson 	if (cpri >= PRI_MIN_IDLE)
436ff256d9cSJeff Roberson 		return (1);
437ff256d9cSJeff Roberson 	/*
438ff256d9cSJeff Roberson 	 * If preemption is disabled don't preempt others.
439ff256d9cSJeff Roberson 	 */
440ff256d9cSJeff Roberson 	if (preempt_thresh == 0)
441ff256d9cSJeff Roberson 		return (0);
442ff256d9cSJeff Roberson 	/*
443ff256d9cSJeff Roberson 	 * Preempt if we exceed the threshold.
444ff256d9cSJeff Roberson 	 */
445ff256d9cSJeff Roberson 	if (pri <= preempt_thresh)
446ff256d9cSJeff Roberson 		return (1);
447ff256d9cSJeff Roberson 	/*
44812d56c0fSJohn Baldwin 	 * If we're interactive or better and there is non-interactive
44912d56c0fSJohn Baldwin 	 * or worse running preempt only remote processors.
450ff256d9cSJeff Roberson 	 */
45112d56c0fSJohn Baldwin 	if (remote && pri <= PRI_MAX_INTERACT && cpri > PRI_MAX_INTERACT)
452ff256d9cSJeff Roberson 		return (1);
453ff256d9cSJeff Roberson 	return (0);
454ff256d9cSJeff Roberson }
455ff256d9cSJeff Roberson 
456ae7a6b38SJeff Roberson /*
457ae7a6b38SJeff Roberson  * Add a thread to the actual run-queue.  Keeps transferable counts up to
458ae7a6b38SJeff Roberson  * date with what is actually on the run-queue.  Selects the correct
459ae7a6b38SJeff Roberson  * queue position for timeshare threads.
460ae7a6b38SJeff Roberson  */
461155b9987SJeff Roberson static __inline void
4629727e637SJeff Roberson tdq_runq_add(struct tdq *tdq, struct thread *td, int flags)
463155b9987SJeff Roberson {
4649727e637SJeff Roberson 	struct td_sched *ts;
465c143ac21SJeff Roberson 	u_char pri;
466c143ac21SJeff Roberson 
467ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
46861a74c5cSJeff Roberson 	THREAD_LOCK_BLOCKED_ASSERT(td, MA_OWNED);
46973daf66fSJeff Roberson 
4709727e637SJeff Roberson 	pri = td->td_priority;
47193ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
4729727e637SJeff Roberson 	TD_SET_RUNQ(td);
4739727e637SJeff Roberson 	if (THREAD_CAN_MIGRATE(td)) {
474d2ad694cSJeff Roberson 		tdq->tdq_transferable++;
475ad1e7d28SJulian Elischer 		ts->ts_flags |= TSF_XFERABLE;
47680f86c9fSJeff Roberson 	}
47712d56c0fSJohn Baldwin 	if (pri < PRI_MIN_BATCH) {
478c143ac21SJeff Roberson 		ts->ts_runq = &tdq->tdq_realtime;
47912d56c0fSJohn Baldwin 	} else if (pri <= PRI_MAX_BATCH) {
480c143ac21SJeff Roberson 		ts->ts_runq = &tdq->tdq_timeshare;
48112d56c0fSJohn Baldwin 		KASSERT(pri <= PRI_MAX_BATCH && pri >= PRI_MIN_BATCH,
482e7d50326SJeff Roberson 			("Invalid priority %d on timeshare runq", pri));
483e7d50326SJeff Roberson 		/*
484e7d50326SJeff Roberson 		 * This queue contains only priorities between MIN and MAX
485e7d50326SJeff Roberson 		 * realtime.  Use the whole queue to represent these values.
486e7d50326SJeff Roberson 		 */
487c47f202bSJeff Roberson 		if ((flags & (SRQ_BORROWING|SRQ_PREEMPTED)) == 0) {
48816705791SAndriy Gapon 			pri = RQ_NQS * (pri - PRI_MIN_BATCH) / PRI_BATCH_RANGE;
489e7d50326SJeff Roberson 			pri = (pri + tdq->tdq_idx) % RQ_NQS;
4903f872f85SJeff Roberson 			/*
4913f872f85SJeff Roberson 			 * This effectively shortens the queue by one so we
4923f872f85SJeff Roberson 			 * can have a one slot difference between idx and
4933f872f85SJeff Roberson 			 * ridx while we wait for threads to drain.
4943f872f85SJeff Roberson 			 */
4953f872f85SJeff Roberson 			if (tdq->tdq_ridx != tdq->tdq_idx &&
4963f872f85SJeff Roberson 			    pri == tdq->tdq_ridx)
4974499aff6SJeff Roberson 				pri = (unsigned char)(pri - 1) % RQ_NQS;
498e7d50326SJeff Roberson 		} else
4993f872f85SJeff Roberson 			pri = tdq->tdq_ridx;
5009727e637SJeff Roberson 		runq_add_pri(ts->ts_runq, td, pri, flags);
501c143ac21SJeff Roberson 		return;
502e7d50326SJeff Roberson 	} else
50373daf66fSJeff Roberson 		ts->ts_runq = &tdq->tdq_idle;
5049727e637SJeff Roberson 	runq_add(ts->ts_runq, td, flags);
50573daf66fSJeff Roberson }
50673daf66fSJeff Roberson 
50773daf66fSJeff Roberson /*
508ae7a6b38SJeff Roberson  * Remove a thread from a run-queue.  This typically happens when a thread
509ae7a6b38SJeff Roberson  * is selected to run.  Running threads are not on the queue and the
510ae7a6b38SJeff Roberson  * transferable count does not reflect them.
511ae7a6b38SJeff Roberson  */
512155b9987SJeff Roberson static __inline void
5139727e637SJeff Roberson tdq_runq_rem(struct tdq *tdq, struct thread *td)
514155b9987SJeff Roberson {
5159727e637SJeff Roberson 	struct td_sched *ts;
5169727e637SJeff Roberson 
51793ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
518ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
51961a74c5cSJeff Roberson 	THREAD_LOCK_BLOCKED_ASSERT(td, MA_OWNED);
520ae7a6b38SJeff Roberson 	KASSERT(ts->ts_runq != NULL,
5219727e637SJeff Roberson 	    ("tdq_runq_remove: thread %p null ts_runq", td));
522ad1e7d28SJulian Elischer 	if (ts->ts_flags & TSF_XFERABLE) {
523d2ad694cSJeff Roberson 		tdq->tdq_transferable--;
524ad1e7d28SJulian Elischer 		ts->ts_flags &= ~TSF_XFERABLE;
52580f86c9fSJeff Roberson 	}
5263f872f85SJeff Roberson 	if (ts->ts_runq == &tdq->tdq_timeshare) {
5273f872f85SJeff Roberson 		if (tdq->tdq_idx != tdq->tdq_ridx)
5289727e637SJeff Roberson 			runq_remove_idx(ts->ts_runq, td, &tdq->tdq_ridx);
529e7d50326SJeff Roberson 		else
5309727e637SJeff Roberson 			runq_remove_idx(ts->ts_runq, td, NULL);
5313f872f85SJeff Roberson 	} else
5329727e637SJeff Roberson 		runq_remove(ts->ts_runq, td);
533155b9987SJeff Roberson }
534155b9987SJeff Roberson 
535ae7a6b38SJeff Roberson /*
536ae7a6b38SJeff Roberson  * Load is maintained for all threads RUNNING and ON_RUNQ.  Add the load
537ae7a6b38SJeff Roberson  * for this thread to the referenced thread queue.
538ae7a6b38SJeff Roberson  */
539a8949de2SJeff Roberson static void
5409727e637SJeff Roberson tdq_load_add(struct tdq *tdq, struct thread *td)
5415d7ef00cSJeff Roberson {
542ae7a6b38SJeff Roberson 
543ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
54461a74c5cSJeff Roberson 	THREAD_LOCK_BLOCKED_ASSERT(td, MA_OWNED);
54503d17db7SJeff Roberson 
546d2ad694cSJeff Roberson 	tdq->tdq_load++;
5471b9d701fSAttilio Rao 	if ((td->td_flags & TDF_NOLOAD) == 0)
548d2ad694cSJeff Roberson 		tdq->tdq_sysload++;
5498f51ad55SJeff Roberson 	KTR_COUNTER0(KTR_SCHED, "load", tdq->tdq_loadname, tdq->tdq_load);
550d9fae5abSAndriy Gapon 	SDT_PROBE2(sched, , , load__change, (int)TDQ_ID(tdq), tdq->tdq_load);
5515d7ef00cSJeff Roberson }
55215dc847eSJeff Roberson 
553ae7a6b38SJeff Roberson /*
554ae7a6b38SJeff Roberson  * Remove the load from a thread that is transitioning to a sleep state or
555ae7a6b38SJeff Roberson  * exiting.
556ae7a6b38SJeff Roberson  */
557a8949de2SJeff Roberson static void
5589727e637SJeff Roberson tdq_load_rem(struct tdq *tdq, struct thread *td)
5595d7ef00cSJeff Roberson {
560ae7a6b38SJeff Roberson 
561ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
56261a74c5cSJeff Roberson 	THREAD_LOCK_BLOCKED_ASSERT(td, MA_OWNED);
563ae7a6b38SJeff Roberson 	KASSERT(tdq->tdq_load != 0,
564c47f202bSJeff Roberson 	    ("tdq_load_rem: Removing with 0 load on queue %d", TDQ_ID(tdq)));
56503d17db7SJeff Roberson 
566d2ad694cSJeff Roberson 	tdq->tdq_load--;
5671b9d701fSAttilio Rao 	if ((td->td_flags & TDF_NOLOAD) == 0)
56803d17db7SJeff Roberson 		tdq->tdq_sysload--;
5698f51ad55SJeff Roberson 	KTR_COUNTER0(KTR_SCHED, "load", tdq->tdq_loadname, tdq->tdq_load);
570d9fae5abSAndriy Gapon 	SDT_PROBE2(sched, , , load__change, (int)TDQ_ID(tdq), tdq->tdq_load);
57115dc847eSJeff Roberson }
57215dc847eSJeff Roberson 
573356500a3SJeff Roberson /*
5745e5c3873SJeff Roberson  * Bound timeshare latency by decreasing slice size as load increases.  We
5755e5c3873SJeff Roberson  * consider the maximum latency as the sum of the threads waiting to run
5765e5c3873SJeff Roberson  * aside from curthread and target no more than sched_slice latency but
5775e5c3873SJeff Roberson  * no less than sched_slice_min runtime.
5785e5c3873SJeff Roberson  */
5795e5c3873SJeff Roberson static inline int
5805e5c3873SJeff Roberson tdq_slice(struct tdq *tdq)
5815e5c3873SJeff Roberson {
5825e5c3873SJeff Roberson 	int load;
5835e5c3873SJeff Roberson 
5845e5c3873SJeff Roberson 	/*
5855e5c3873SJeff Roberson 	 * It is safe to use sys_load here because this is called from
5865e5c3873SJeff Roberson 	 * contexts where timeshare threads are running and so there
5875e5c3873SJeff Roberson 	 * cannot be higher priority load in the system.
5885e5c3873SJeff Roberson 	 */
5895e5c3873SJeff Roberson 	load = tdq->tdq_sysload - 1;
5905e5c3873SJeff Roberson 	if (load >= SCHED_SLICE_MIN_DIVISOR)
5915e5c3873SJeff Roberson 		return (sched_slice_min);
5925e5c3873SJeff Roberson 	if (load <= 1)
5935e5c3873SJeff Roberson 		return (sched_slice);
5945e5c3873SJeff Roberson 	return (sched_slice / load);
5955e5c3873SJeff Roberson }
5965e5c3873SJeff Roberson 
5975e5c3873SJeff Roberson /*
59862fa74d9SJeff Roberson  * Set lowpri to its exact value by searching the run-queue and
59962fa74d9SJeff Roberson  * evaluating curthread.  curthread may be passed as an optimization.
600356500a3SJeff Roberson  */
60122bf7d9aSJeff Roberson static void
60262fa74d9SJeff Roberson tdq_setlowpri(struct tdq *tdq, struct thread *ctd)
60362fa74d9SJeff Roberson {
60462fa74d9SJeff Roberson 	struct thread *td;
60562fa74d9SJeff Roberson 
60662fa74d9SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
60762fa74d9SJeff Roberson 	if (ctd == NULL)
60862fa74d9SJeff Roberson 		ctd = pcpu_find(TDQ_ID(tdq))->pc_curthread;
6099727e637SJeff Roberson 	td = tdq_choose(tdq);
6109727e637SJeff Roberson 	if (td == NULL || td->td_priority > ctd->td_priority)
61162fa74d9SJeff Roberson 		tdq->tdq_lowpri = ctd->td_priority;
61262fa74d9SJeff Roberson 	else
61362fa74d9SJeff Roberson 		tdq->tdq_lowpri = td->td_priority;
61462fa74d9SJeff Roberson }
61562fa74d9SJeff Roberson 
61662fa74d9SJeff Roberson #ifdef SMP
6179129dd59SPedro F. Giffuni /*
6189129dd59SPedro F. Giffuni  * We need some randomness. Implement a classic Linear Congruential
6199129dd59SPedro F. Giffuni  * Generator X_{n+1}=(aX_n+c) mod m. These values are optimized for
6209129dd59SPedro F. Giffuni  * m = 2^32, a = 69069 and c = 5. We only return the upper 16 bits
6219129dd59SPedro F. Giffuni  * of the random state (in the low bits of our answer) to keep
6229129dd59SPedro F. Giffuni  * the maximum randomness.
6239129dd59SPedro F. Giffuni  */
6249129dd59SPedro F. Giffuni static uint32_t
6259129dd59SPedro F. Giffuni sched_random(void)
6269129dd59SPedro F. Giffuni {
6279129dd59SPedro F. Giffuni 	uint32_t *rndptr;
6289129dd59SPedro F. Giffuni 
6299129dd59SPedro F. Giffuni 	rndptr = DPCPU_PTR(randomval);
6309129dd59SPedro F. Giffuni 	*rndptr = *rndptr * 69069 + 5;
6319129dd59SPedro F. Giffuni 
6329129dd59SPedro F. Giffuni 	return (*rndptr >> 16);
6339129dd59SPedro F. Giffuni }
6349129dd59SPedro F. Giffuni 
63562fa74d9SJeff Roberson struct cpu_search {
636aefe0a8cSAlexander Motin 	cpuset_t *cs_mask;
63736acfc65SAlexander Motin 	u_int	cs_prefer;
63836acfc65SAlexander Motin 	int	cs_pri;		/* Min priority for low. */
63936acfc65SAlexander Motin 	int	cs_limit;	/* Max load for low, min load for high. */
640aefe0a8cSAlexander Motin };
641aefe0a8cSAlexander Motin 
642aefe0a8cSAlexander Motin struct cpu_search_res {
64336acfc65SAlexander Motin 	int	cs_cpu;
64436acfc65SAlexander Motin 	int	cs_load;
64562fa74d9SJeff Roberson };
64662fa74d9SJeff Roberson 
64762fa74d9SJeff Roberson /*
648aefe0a8cSAlexander Motin  * Search the tree of cpu_groups for the lowest or highest loaded CPU.
649aefe0a8cSAlexander Motin  * These routines actually compare the load on all paths through the tree
650aefe0a8cSAlexander Motin  * and find the least loaded cpu on the least loaded path, which may differ
651aefe0a8cSAlexander Motin  * from the least loaded cpu in the system.  This balances work among caches
652aefe0a8cSAlexander Motin  * and buses.
65362fa74d9SJeff Roberson  */
654aefe0a8cSAlexander Motin static int
655aefe0a8cSAlexander Motin cpu_search_lowest(const struct cpu_group *cg, const struct cpu_search *s,
656aefe0a8cSAlexander Motin     struct cpu_search_res *r)
65762fa74d9SJeff Roberson {
658aefe0a8cSAlexander Motin 	struct cpu_search_res lr;
65936acfc65SAlexander Motin 	struct tdq *tdq;
660aefe0a8cSAlexander Motin 	int c, bload, l, load, total;
66162fa74d9SJeff Roberson 
66236acfc65SAlexander Motin 	total = 0;
663aefe0a8cSAlexander Motin 	bload = INT_MAX;
664aefe0a8cSAlexander Motin 	r->cs_cpu = -1;
66536acfc65SAlexander Motin 
666aefe0a8cSAlexander Motin 	/* Loop through children CPU groups if there are any. */
667aefe0a8cSAlexander Motin 	if (cg->cg_children > 0) {
668aefe0a8cSAlexander Motin 		for (c = cg->cg_children - 1; c >= 0; c--) {
669aefe0a8cSAlexander Motin 			load = cpu_search_lowest(&cg->cg_child[c], s, &lr);
67036acfc65SAlexander Motin 			total += load;
671aefe0a8cSAlexander Motin 			if (lr.cs_cpu >= 0 && (load < bload ||
672aefe0a8cSAlexander Motin 			    (load == bload && lr.cs_load < r->cs_load))) {
673aefe0a8cSAlexander Motin 				bload = load;
674aefe0a8cSAlexander Motin 				r->cs_cpu = lr.cs_cpu;
675aefe0a8cSAlexander Motin 				r->cs_load = lr.cs_load;
67636acfc65SAlexander Motin 			}
67736acfc65SAlexander Motin 		}
67862fa74d9SJeff Roberson 		return (total);
67962fa74d9SJeff Roberson 	}
68062fa74d9SJeff Roberson 
681aefe0a8cSAlexander Motin 	/* Loop through children CPUs otherwise. */
682aefe0a8cSAlexander Motin 	for (c = cg->cg_last; c >= cg->cg_first; c--) {
683aefe0a8cSAlexander Motin 		if (!CPU_ISSET(c, &cg->cg_mask))
684aefe0a8cSAlexander Motin 			continue;
685aefe0a8cSAlexander Motin 		tdq = TDQ_CPU(c);
686aefe0a8cSAlexander Motin 		l = tdq->tdq_load;
687aefe0a8cSAlexander Motin 		load = l * 256;
688aefe0a8cSAlexander Motin 		if (c == s->cs_prefer)
689aefe0a8cSAlexander Motin 			load -= 128;
690aefe0a8cSAlexander Motin 		total += load;
691aefe0a8cSAlexander Motin 		if (l > s->cs_limit || tdq->tdq_lowpri <= s->cs_pri ||
692aefe0a8cSAlexander Motin 		    !CPU_ISSET(c, s->cs_mask))
693aefe0a8cSAlexander Motin 			continue;
694aefe0a8cSAlexander Motin 		load -= sched_random() % 128;
695aefe0a8cSAlexander Motin 		if (load < bload) {
696aefe0a8cSAlexander Motin 			bload = load;
697aefe0a8cSAlexander Motin 			r->cs_cpu = c;
698aefe0a8cSAlexander Motin 		}
699aefe0a8cSAlexander Motin 	}
700aefe0a8cSAlexander Motin 	r->cs_load = bload;
701aefe0a8cSAlexander Motin 	return (total);
70262fa74d9SJeff Roberson }
70362fa74d9SJeff Roberson 
704aefe0a8cSAlexander Motin static int
705aefe0a8cSAlexander Motin cpu_search_highest(const struct cpu_group *cg, const struct cpu_search *s,
706aefe0a8cSAlexander Motin     struct cpu_search_res *r)
70762fa74d9SJeff Roberson {
708aefe0a8cSAlexander Motin 	struct cpu_search_res lr;
709aefe0a8cSAlexander Motin 	struct tdq *tdq;
710aefe0a8cSAlexander Motin 	int c, bload, l, load, total;
711aefe0a8cSAlexander Motin 
712aefe0a8cSAlexander Motin 	total = 0;
713aefe0a8cSAlexander Motin 	bload = INT_MIN;
714aefe0a8cSAlexander Motin 	r->cs_cpu = -1;
715aefe0a8cSAlexander Motin 
716aefe0a8cSAlexander Motin 	/* Loop through children CPU groups if there are any. */
717aefe0a8cSAlexander Motin 	if (cg->cg_children > 0) {
718aefe0a8cSAlexander Motin 		for (c = cg->cg_children - 1; c >= 0; c--) {
719aefe0a8cSAlexander Motin 			load = cpu_search_highest(&cg->cg_child[c], s, &lr);
720aefe0a8cSAlexander Motin 			total += load;
721aefe0a8cSAlexander Motin 			if (lr.cs_cpu >= 0 && (load > bload ||
722aefe0a8cSAlexander Motin 			    (load == bload && lr.cs_load > r->cs_load))) {
723aefe0a8cSAlexander Motin 				bload = load;
724aefe0a8cSAlexander Motin 				r->cs_cpu = lr.cs_cpu;
725aefe0a8cSAlexander Motin 				r->cs_load = lr.cs_load;
726aefe0a8cSAlexander Motin 			}
727aefe0a8cSAlexander Motin 		}
728aefe0a8cSAlexander Motin 		return (total);
72962fa74d9SJeff Roberson 	}
73062fa74d9SJeff Roberson 
731aefe0a8cSAlexander Motin 	/* Loop through children CPUs otherwise. */
732aefe0a8cSAlexander Motin 	for (c = cg->cg_last; c >= cg->cg_first; c--) {
733aefe0a8cSAlexander Motin 		if (!CPU_ISSET(c, &cg->cg_mask))
734aefe0a8cSAlexander Motin 			continue;
735aefe0a8cSAlexander Motin 		tdq = TDQ_CPU(c);
736aefe0a8cSAlexander Motin 		l = tdq->tdq_load;
737aefe0a8cSAlexander Motin 		load = l * 256;
738aefe0a8cSAlexander Motin 		total += load;
739aefe0a8cSAlexander Motin 		if (l < s->cs_limit || !tdq->tdq_transferable ||
740aefe0a8cSAlexander Motin 		    !CPU_ISSET(c, s->cs_mask))
741aefe0a8cSAlexander Motin 			continue;
742aefe0a8cSAlexander Motin 		load -= sched_random() % 128;
743aefe0a8cSAlexander Motin 		if (load > bload) {
744aefe0a8cSAlexander Motin 			bload = load;
745aefe0a8cSAlexander Motin 			r->cs_cpu = c;
746aefe0a8cSAlexander Motin 		}
747aefe0a8cSAlexander Motin 	}
748aefe0a8cSAlexander Motin 	r->cs_load = bload;
749aefe0a8cSAlexander Motin 	return (total);
75062fa74d9SJeff Roberson }
75162fa74d9SJeff Roberson 
75262fa74d9SJeff Roberson /*
75362fa74d9SJeff Roberson  * Find the cpu with the least load via the least loaded path that has a
75462fa74d9SJeff Roberson  * lowpri greater than pri  pri.  A pri of -1 indicates any priority is
75562fa74d9SJeff Roberson  * acceptable.
75662fa74d9SJeff Roberson  */
75762fa74d9SJeff Roberson static inline int
758aefe0a8cSAlexander Motin sched_lowest(const struct cpu_group *cg, cpuset_t *mask, int pri, int maxload,
75936acfc65SAlexander Motin     int prefer)
76062fa74d9SJeff Roberson {
761aefe0a8cSAlexander Motin 	struct cpu_search s;
762aefe0a8cSAlexander Motin 	struct cpu_search_res r;
76362fa74d9SJeff Roberson 
764aefe0a8cSAlexander Motin 	s.cs_prefer = prefer;
765aefe0a8cSAlexander Motin 	s.cs_mask = mask;
766aefe0a8cSAlexander Motin 	s.cs_pri = pri;
767aefe0a8cSAlexander Motin 	s.cs_limit = maxload;
768aefe0a8cSAlexander Motin 	cpu_search_lowest(cg, &s, &r);
769aefe0a8cSAlexander Motin 	return (r.cs_cpu);
77062fa74d9SJeff Roberson }
77162fa74d9SJeff Roberson 
77262fa74d9SJeff Roberson /*
77362fa74d9SJeff Roberson  * Find the cpu with the highest load via the highest loaded path.
77462fa74d9SJeff Roberson  */
77562fa74d9SJeff Roberson static inline int
776aefe0a8cSAlexander Motin sched_highest(const struct cpu_group *cg, cpuset_t *mask, int minload)
77762fa74d9SJeff Roberson {
778aefe0a8cSAlexander Motin 	struct cpu_search s;
779aefe0a8cSAlexander Motin 	struct cpu_search_res r;
78062fa74d9SJeff Roberson 
781aefe0a8cSAlexander Motin 	s.cs_mask = mask;
782aefe0a8cSAlexander Motin 	s.cs_limit = minload;
783aefe0a8cSAlexander Motin 	cpu_search_highest(cg, &s, &r);
784aefe0a8cSAlexander Motin 	return (r.cs_cpu);
78562fa74d9SJeff Roberson }
78662fa74d9SJeff Roberson 
78762fa74d9SJeff Roberson static void
78862fa74d9SJeff Roberson sched_balance_group(struct cpu_group *cg)
78962fa74d9SJeff Roberson {
790018ff686SJeff Roberson 	struct tdq *tdq;
79136acfc65SAlexander Motin 	cpuset_t hmask, lmask;
79236acfc65SAlexander Motin 	int high, low, anylow;
79362fa74d9SJeff Roberson 
79436acfc65SAlexander Motin 	CPU_FILL(&hmask);
79562fa74d9SJeff Roberson 	for (;;) {
796aefe0a8cSAlexander Motin 		high = sched_highest(cg, &hmask, 2);
79736acfc65SAlexander Motin 		/* Stop if there is no more CPU with transferrable threads. */
79836acfc65SAlexander Motin 		if (high == -1)
79962fa74d9SJeff Roberson 			break;
80036acfc65SAlexander Motin 		CPU_CLR(high, &hmask);
80136acfc65SAlexander Motin 		CPU_COPY(&hmask, &lmask);
80236acfc65SAlexander Motin 		/* Stop if there is no more CPU left for low. */
80336acfc65SAlexander Motin 		if (CPU_EMPTY(&lmask))
80462fa74d9SJeff Roberson 			break;
80536acfc65SAlexander Motin 		anylow = 1;
806018ff686SJeff Roberson 		tdq = TDQ_CPU(high);
80736acfc65SAlexander Motin nextlow:
808aefe0a8cSAlexander Motin 		low = sched_lowest(cg, &lmask, -1, tdq->tdq_load - 1, high);
80936acfc65SAlexander Motin 		/* Stop if we looked well and found no less loaded CPU. */
81036acfc65SAlexander Motin 		if (anylow && low == -1)
81136acfc65SAlexander Motin 			break;
81236acfc65SAlexander Motin 		/* Go to next high if we found no less loaded CPU. */
81336acfc65SAlexander Motin 		if (low == -1)
81436acfc65SAlexander Motin 			continue;
81536acfc65SAlexander Motin 		/* Transfer thread from high to low. */
816018ff686SJeff Roberson 		if (sched_balance_pair(tdq, TDQ_CPU(low))) {
81736acfc65SAlexander Motin 			/* CPU that got thread can no longer be a donor. */
81836acfc65SAlexander Motin 			CPU_CLR(low, &hmask);
81936acfc65SAlexander Motin 		} else {
82062fa74d9SJeff Roberson 			/*
82136acfc65SAlexander Motin 			 * If failed, then there is no threads on high
82236acfc65SAlexander Motin 			 * that can run on this low. Drop low from low
82336acfc65SAlexander Motin 			 * mask and look for different one.
82462fa74d9SJeff Roberson 			 */
82536acfc65SAlexander Motin 			CPU_CLR(low, &lmask);
82636acfc65SAlexander Motin 			anylow = 0;
82736acfc65SAlexander Motin 			goto nextlow;
82862fa74d9SJeff Roberson 		}
82936acfc65SAlexander Motin 	}
83062fa74d9SJeff Roberson }
83162fa74d9SJeff Roberson 
83262fa74d9SJeff Roberson static void
83362375ca8SEd Schouten sched_balance(void)
834356500a3SJeff Roberson {
8357fcf154aSJeff Roberson 	struct tdq *tdq;
836356500a3SJeff Roberson 
8370567b6ccSWarner Losh 	balance_ticks = max(balance_interval / 2, 1) +
838b250ad34SWarner Losh 	    (sched_random() % balance_interval);
8397fcf154aSJeff Roberson 	tdq = TDQ_SELF();
8407fcf154aSJeff Roberson 	TDQ_UNLOCK(tdq);
84162fa74d9SJeff Roberson 	sched_balance_group(cpu_top);
8427fcf154aSJeff Roberson 	TDQ_LOCK(tdq);
843cac77d04SJeff Roberson }
84486f8ae96SJeff Roberson 
845ae7a6b38SJeff Roberson /*
846ae7a6b38SJeff Roberson  * Lock two thread queues using their address to maintain lock order.
847ae7a6b38SJeff Roberson  */
848ae7a6b38SJeff Roberson static void
849ae7a6b38SJeff Roberson tdq_lock_pair(struct tdq *one, struct tdq *two)
850ae7a6b38SJeff Roberson {
851ae7a6b38SJeff Roberson 	if (one < two) {
852ae7a6b38SJeff Roberson 		TDQ_LOCK(one);
853ae7a6b38SJeff Roberson 		TDQ_LOCK_FLAGS(two, MTX_DUPOK);
854ae7a6b38SJeff Roberson 	} else {
855ae7a6b38SJeff Roberson 		TDQ_LOCK(two);
856ae7a6b38SJeff Roberson 		TDQ_LOCK_FLAGS(one, MTX_DUPOK);
857ae7a6b38SJeff Roberson 	}
858ae7a6b38SJeff Roberson }
859ae7a6b38SJeff Roberson 
860ae7a6b38SJeff Roberson /*
8617fcf154aSJeff Roberson  * Unlock two thread queues.  Order is not important here.
8627fcf154aSJeff Roberson  */
8637fcf154aSJeff Roberson static void
8647fcf154aSJeff Roberson tdq_unlock_pair(struct tdq *one, struct tdq *two)
8657fcf154aSJeff Roberson {
8667fcf154aSJeff Roberson 	TDQ_UNLOCK(one);
8677fcf154aSJeff Roberson 	TDQ_UNLOCK(two);
8687fcf154aSJeff Roberson }
8697fcf154aSJeff Roberson 
8707fcf154aSJeff Roberson /*
871ae7a6b38SJeff Roberson  * Transfer load between two imbalanced thread queues.
872ae7a6b38SJeff Roberson  */
87362fa74d9SJeff Roberson static int
874ad1e7d28SJulian Elischer sched_balance_pair(struct tdq *high, struct tdq *low)
875cac77d04SJeff Roberson {
87697e9382dSDon Lewis 	struct thread *td;
877880bf8b9SMarius Strobl 	int cpu;
878cac77d04SJeff Roberson 
879ae7a6b38SJeff Roberson 	tdq_lock_pair(high, low);
88097e9382dSDon Lewis 	td = NULL;
881155b9987SJeff Roberson 	/*
88297e9382dSDon Lewis 	 * Transfer a thread from high to low.
883155b9987SJeff Roberson 	 */
88436acfc65SAlexander Motin 	if (high->tdq_transferable != 0 && high->tdq_load > low->tdq_load &&
88597e9382dSDon Lewis 	    (td = tdq_move(high, low)) != NULL) {
886a5423ea3SJeff Roberson 		/*
88797e9382dSDon Lewis 		 * In case the target isn't the current cpu notify it of the
88897e9382dSDon Lewis 		 * new load, possibly sending an IPI to force it to reschedule.
889a5423ea3SJeff Roberson 		 */
890880bf8b9SMarius Strobl 		cpu = TDQ_ID(low);
891880bf8b9SMarius Strobl 		if (cpu != PCPU_GET(cpuid))
89297e9382dSDon Lewis 			tdq_notify(low, td);
893ae7a6b38SJeff Roberson 	}
8947fcf154aSJeff Roberson 	tdq_unlock_pair(high, low);
89597e9382dSDon Lewis 	return (td != NULL);
896356500a3SJeff Roberson }
897356500a3SJeff Roberson 
898ae7a6b38SJeff Roberson /*
899ae7a6b38SJeff Roberson  * Move a thread from one thread queue to another.
900ae7a6b38SJeff Roberson  */
90197e9382dSDon Lewis static struct thread *
902ae7a6b38SJeff Roberson tdq_move(struct tdq *from, struct tdq *to)
903356500a3SJeff Roberson {
904ae7a6b38SJeff Roberson 	struct thread *td;
905ae7a6b38SJeff Roberson 	struct tdq *tdq;
906ae7a6b38SJeff Roberson 	int cpu;
907356500a3SJeff Roberson 
9087fcf154aSJeff Roberson 	TDQ_LOCK_ASSERT(from, MA_OWNED);
9097fcf154aSJeff Roberson 	TDQ_LOCK_ASSERT(to, MA_OWNED);
9107fcf154aSJeff Roberson 
911ad1e7d28SJulian Elischer 	tdq = from;
912ae7a6b38SJeff Roberson 	cpu = TDQ_ID(to);
9139727e637SJeff Roberson 	td = tdq_steal(tdq, cpu);
9149727e637SJeff Roberson 	if (td == NULL)
91597e9382dSDon Lewis 		return (NULL);
91661a74c5cSJeff Roberson 
917ae7a6b38SJeff Roberson 	/*
91861a74c5cSJeff Roberson 	 * Although the run queue is locked the thread may be
91961a74c5cSJeff Roberson 	 * blocked.  We can not set the lock until it is unblocked.
920ae7a6b38SJeff Roberson 	 */
92161a74c5cSJeff Roberson 	thread_lock_block_wait(td);
922ae7a6b38SJeff Roberson 	sched_rem(td);
92361a74c5cSJeff Roberson 	THREAD_LOCKPTR_ASSERT(td, TDQ_LOCKPTR(from));
924ae7a6b38SJeff Roberson 	td->td_lock = TDQ_LOCKPTR(to);
92561a74c5cSJeff Roberson 	td_get_sched(td)->ts_cpu = cpu;
926ae7a6b38SJeff Roberson 	tdq_add(to, td, SRQ_YIELDING);
92761a74c5cSJeff Roberson 
92897e9382dSDon Lewis 	return (td);
929356500a3SJeff Roberson }
93022bf7d9aSJeff Roberson 
931ae7a6b38SJeff Roberson /*
932ae7a6b38SJeff Roberson  * This tdq has idled.  Try to steal a thread from another cpu and switch
933ae7a6b38SJeff Roberson  * to it.
934ae7a6b38SJeff Roberson  */
93580f86c9fSJeff Roberson static int
936ad1e7d28SJulian Elischer tdq_idled(struct tdq *tdq)
93722bf7d9aSJeff Roberson {
9382668bb2aSAlexander Motin 	struct cpu_group *cg, *parent;
939ad1e7d28SJulian Elischer 	struct tdq *steal;
940c76ee827SJeff Roberson 	cpuset_t mask;
9412668bb2aSAlexander Motin 	int cpu, switchcnt, goup;
94280f86c9fSJeff Roberson 
94397e9382dSDon Lewis 	if (smp_started == 0 || steal_idle == 0 || tdq->tdq_cg == NULL)
94488f530ccSJeff Roberson 		return (1);
945c76ee827SJeff Roberson 	CPU_FILL(&mask);
946c76ee827SJeff Roberson 	CPU_CLR(PCPU_GET(cpuid), &mask);
94797e9382dSDon Lewis     restart:
94897e9382dSDon Lewis 	switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
9492668bb2aSAlexander Motin 	for (cg = tdq->tdq_cg, goup = 0; ; ) {
950aefe0a8cSAlexander Motin 		cpu = sched_highest(cg, &mask, steal_thresh);
95197e9382dSDon Lewis 		/*
95297e9382dSDon Lewis 		 * We were assigned a thread but not preempted.  Returning
95397e9382dSDon Lewis 		 * 0 here will cause our caller to switch to it.
95497e9382dSDon Lewis 		 */
95597e9382dSDon Lewis 		if (tdq->tdq_load)
95697e9382dSDon Lewis 			return (0);
9572668bb2aSAlexander Motin 
9582668bb2aSAlexander Motin 		/*
9592668bb2aSAlexander Motin 		 * We found no CPU to steal from in this group.  Escalate to
9602668bb2aSAlexander Motin 		 * the parent and repeat.  But if parent has only two children
9612668bb2aSAlexander Motin 		 * groups we can avoid searching this group again by searching
9622668bb2aSAlexander Motin 		 * the other one specifically and then escalating two levels.
9632668bb2aSAlexander Motin 		 */
96462fa74d9SJeff Roberson 		if (cpu == -1) {
9652668bb2aSAlexander Motin 			if (goup) {
96662fa74d9SJeff Roberson 				cg = cg->cg_parent;
9672668bb2aSAlexander Motin 				goup = 0;
9682668bb2aSAlexander Motin 			}
9692668bb2aSAlexander Motin 			parent = cg->cg_parent;
9702668bb2aSAlexander Motin 			if (parent == NULL)
97197e9382dSDon Lewis 				return (1);
9722668bb2aSAlexander Motin 			if (parent->cg_children == 2) {
9732668bb2aSAlexander Motin 				if (cg == &parent->cg_child[0])
9742668bb2aSAlexander Motin 					cg = &parent->cg_child[1];
9752668bb2aSAlexander Motin 				else
9762668bb2aSAlexander Motin 					cg = &parent->cg_child[0];
9772668bb2aSAlexander Motin 				goup = 1;
9782668bb2aSAlexander Motin 			} else
9792668bb2aSAlexander Motin 				cg = parent;
98080f86c9fSJeff Roberson 			continue;
9817b8bfa0dSJeff Roberson 		}
9827b8bfa0dSJeff Roberson 		steal = TDQ_CPU(cpu);
98397e9382dSDon Lewis 		/*
98497e9382dSDon Lewis 		 * The data returned by sched_highest() is stale and
98597e9382dSDon Lewis 		 * the chosen CPU no longer has an eligible thread.
98697e9382dSDon Lewis 		 *
98797e9382dSDon Lewis 		 * Testing this ahead of tdq_lock_pair() only catches
98897e9382dSDon Lewis 		 * this situation about 20% of the time on an 8 core
98997e9382dSDon Lewis 		 * 16 thread Ryzen 7, but it still helps performance.
99097e9382dSDon Lewis 		 */
99197e9382dSDon Lewis 		if (steal->tdq_load < steal_thresh ||
99297e9382dSDon Lewis 		    steal->tdq_transferable == 0)
99397e9382dSDon Lewis 			goto restart;
99497e9382dSDon Lewis 		/*
995*8bb173fbSAlexander Motin 		 * Try to lock both queues. If we are assigned a thread while
996*8bb173fbSAlexander Motin 		 * waited for the lock, switch to it now instead of stealing.
997*8bb173fbSAlexander Motin 		 * If we can't get the lock, then somebody likely got there
998*8bb173fbSAlexander Motin 		 * first so continue searching.
99997e9382dSDon Lewis 		 */
1000*8bb173fbSAlexander Motin 		TDQ_LOCK(tdq);
1001*8bb173fbSAlexander Motin 		if (tdq->tdq_load > 0) {
1002*8bb173fbSAlexander Motin 			mi_switch(SW_VOL | SWT_IDLE);
1003*8bb173fbSAlexander Motin 			return (0);
1004*8bb173fbSAlexander Motin 		}
1005*8bb173fbSAlexander Motin 		if (TDQ_TRYLOCK_FLAGS(steal, MTX_DUPOK) == 0) {
1006*8bb173fbSAlexander Motin 			TDQ_UNLOCK(tdq);
1007*8bb173fbSAlexander Motin 			CPU_CLR(cpu, &mask);
1008*8bb173fbSAlexander Motin 			continue;
1009*8bb173fbSAlexander Motin 		}
101097e9382dSDon Lewis 		/*
101197e9382dSDon Lewis 		 * The data returned by sched_highest() is stale and
101297e9382dSDon Lewis 		 * the chosen CPU no longer has an eligible thread, or
101397e9382dSDon Lewis 		 * we were preempted and the CPU loading info may be out
101497e9382dSDon Lewis 		 * of date.  The latter is rare.  In either case restart
101597e9382dSDon Lewis 		 * the search.
101697e9382dSDon Lewis 		 */
101797e9382dSDon Lewis 		if (steal->tdq_load < steal_thresh ||
101897e9382dSDon Lewis 		    steal->tdq_transferable == 0 ||
101997e9382dSDon Lewis 		    switchcnt != tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt) {
10207fcf154aSJeff Roberson 			tdq_unlock_pair(tdq, steal);
102197e9382dSDon Lewis 			goto restart;
102262fa74d9SJeff Roberson 		}
102362fa74d9SJeff Roberson 		/*
102497e9382dSDon Lewis 		 * Steal the thread and switch to it.
102562fa74d9SJeff Roberson 		 */
102697e9382dSDon Lewis 		if (tdq_move(steal, tdq) != NULL)
102797e9382dSDon Lewis 			break;
102897e9382dSDon Lewis 		/*
102997e9382dSDon Lewis 		 * We failed to acquire a thread even though it looked
103097e9382dSDon Lewis 		 * like one was available.  This could be due to affinity
103197e9382dSDon Lewis 		 * restrictions or for other reasons.  Loop again after
103297e9382dSDon Lewis 		 * removing this CPU from the set.  The restart logic
103397e9382dSDon Lewis 		 * above does not restore this CPU to the set due to the
103497e9382dSDon Lewis 		 * likelyhood of failing here again.
103597e9382dSDon Lewis 		 */
103697e9382dSDon Lewis 		CPU_CLR(cpu, &mask);
103762fa74d9SJeff Roberson 		tdq_unlock_pair(tdq, steal);
103880f86c9fSJeff Roberson 	}
1039ae7a6b38SJeff Roberson 	TDQ_UNLOCK(steal);
1040686bcb5cSJeff Roberson 	mi_switch(SW_VOL | SWT_IDLE);
10417b8bfa0dSJeff Roberson 	return (0);
104222bf7d9aSJeff Roberson }
104322bf7d9aSJeff Roberson 
1044ae7a6b38SJeff Roberson /*
1045ae7a6b38SJeff Roberson  * Notify a remote cpu of new work.  Sends an IPI if criteria are met.
1046ae7a6b38SJeff Roberson  */
104722bf7d9aSJeff Roberson static void
104827ee18adSRyan Stone tdq_notify(struct tdq *tdq, struct thread *td)
104922bf7d9aSJeff Roberson {
105002f0ff6dSJohn Baldwin 	struct thread *ctd;
105127ee18adSRyan Stone 	int pri;
10527b8bfa0dSJeff Roberson 	int cpu;
105322bf7d9aSJeff Roberson 
10547789ab32SMark Johnston 	if (tdq->tdq_owepreempt)
1055ff256d9cSJeff Roberson 		return;
105627ee18adSRyan Stone 	cpu = td_get_sched(td)->ts_cpu;
105727ee18adSRyan Stone 	pri = td->td_priority;
105802f0ff6dSJohn Baldwin 	ctd = pcpu_find(cpu)->pc_curthread;
105902f0ff6dSJohn Baldwin 	if (!sched_shouldpreempt(pri, ctd->td_priority, 1))
10606b2f763fSJeff Roberson 		return;
106179654969SAlexander Motin 
106279654969SAlexander Motin 	/*
1063ae9e9b4fSAlexander Motin 	 * Make sure that our caller's earlier update to tdq_load is
1064ae9e9b4fSAlexander Motin 	 * globally visible before we read tdq_cpu_idle.  Idle thread
106579654969SAlexander Motin 	 * accesses both of them without locks, and the order is important.
106679654969SAlexander Motin 	 */
1067e8677f38SKonstantin Belousov 	atomic_thread_fence_seq_cst();
106879654969SAlexander Motin 
106902f0ff6dSJohn Baldwin 	if (TD_IS_IDLETHREAD(ctd)) {
10701690c6c1SJeff Roberson 		/*
10716c47aaaeSJeff Roberson 		 * If the MD code has an idle wakeup routine try that before
10726c47aaaeSJeff Roberson 		 * falling back to IPI.
10736c47aaaeSJeff Roberson 		 */
10749f9ad565SAlexander Motin 		if (!tdq->tdq_cpu_idle || cpu_idle_wakeup(cpu))
10756c47aaaeSJeff Roberson 			return;
10761690c6c1SJeff Roberson 	}
10777789ab32SMark Johnston 
10787789ab32SMark Johnston 	/*
10797789ab32SMark Johnston 	 * The run queues have been updated, so any switch on the remote CPU
10807789ab32SMark Johnston 	 * will satisfy the preemption request.
10817789ab32SMark Johnston 	 */
10827789ab32SMark Johnston 	tdq->tdq_owepreempt = 1;
1083d9d8d144SJohn Baldwin 	ipi_cpu(cpu, IPI_PREEMPT);
108422bf7d9aSJeff Roberson }
108522bf7d9aSJeff Roberson 
1086ae7a6b38SJeff Roberson /*
1087ae7a6b38SJeff Roberson  * Steals load from a timeshare queue.  Honors the rotating queue head
1088ae7a6b38SJeff Roberson  * index.
1089ae7a6b38SJeff Roberson  */
10909727e637SJeff Roberson static struct thread *
109162fa74d9SJeff Roberson runq_steal_from(struct runq *rq, int cpu, u_char start)
1092ae7a6b38SJeff Roberson {
1093ae7a6b38SJeff Roberson 	struct rqbits *rqb;
1094ae7a6b38SJeff Roberson 	struct rqhead *rqh;
109536acfc65SAlexander Motin 	struct thread *td, *first;
1096ae7a6b38SJeff Roberson 	int bit;
1097ae7a6b38SJeff Roberson 	int i;
1098ae7a6b38SJeff Roberson 
1099ae7a6b38SJeff Roberson 	rqb = &rq->rq_status;
1100ae7a6b38SJeff Roberson 	bit = start & (RQB_BPW -1);
110136acfc65SAlexander Motin 	first = NULL;
1102ae7a6b38SJeff Roberson again:
1103ae7a6b38SJeff Roberson 	for (i = RQB_WORD(start); i < RQB_LEN; bit = 0, i++) {
1104ae7a6b38SJeff Roberson 		if (rqb->rqb_bits[i] == 0)
1105ae7a6b38SJeff Roberson 			continue;
11068bc713f6SJeff Roberson 		if (bit == 0)
11078bc713f6SJeff Roberson 			bit = RQB_FFS(rqb->rqb_bits[i]);
11088bc713f6SJeff Roberson 		for (; bit < RQB_BPW; bit++) {
11098bc713f6SJeff Roberson 			if ((rqb->rqb_bits[i] & (1ul << bit)) == 0)
1110ae7a6b38SJeff Roberson 				continue;
11118bc713f6SJeff Roberson 			rqh = &rq->rq_queues[bit + (i << RQB_L2BPW)];
11129727e637SJeff Roberson 			TAILQ_FOREACH(td, rqh, td_runq) {
11139727e637SJeff Roberson 				if (first && THREAD_CAN_MIGRATE(td) &&
11149727e637SJeff Roberson 				    THREAD_CAN_SCHED(td, cpu))
11159727e637SJeff Roberson 					return (td);
111636acfc65SAlexander Motin 				first = td;
1117ae7a6b38SJeff Roberson 			}
1118ae7a6b38SJeff Roberson 		}
11198bc713f6SJeff Roberson 	}
1120ae7a6b38SJeff Roberson 	if (start != 0) {
1121ae7a6b38SJeff Roberson 		start = 0;
1122ae7a6b38SJeff Roberson 		goto again;
1123ae7a6b38SJeff Roberson 	}
1124ae7a6b38SJeff Roberson 
112536acfc65SAlexander Motin 	if (first && THREAD_CAN_MIGRATE(first) &&
112636acfc65SAlexander Motin 	    THREAD_CAN_SCHED(first, cpu))
112736acfc65SAlexander Motin 		return (first);
1128ae7a6b38SJeff Roberson 	return (NULL);
1129ae7a6b38SJeff Roberson }
1130ae7a6b38SJeff Roberson 
1131ae7a6b38SJeff Roberson /*
1132ae7a6b38SJeff Roberson  * Steals load from a standard linear queue.
1133ae7a6b38SJeff Roberson  */
11349727e637SJeff Roberson static struct thread *
113562fa74d9SJeff Roberson runq_steal(struct runq *rq, int cpu)
113622bf7d9aSJeff Roberson {
113722bf7d9aSJeff Roberson 	struct rqhead *rqh;
113822bf7d9aSJeff Roberson 	struct rqbits *rqb;
11399727e637SJeff Roberson 	struct thread *td;
114022bf7d9aSJeff Roberson 	int word;
114122bf7d9aSJeff Roberson 	int bit;
114222bf7d9aSJeff Roberson 
114322bf7d9aSJeff Roberson 	rqb = &rq->rq_status;
114422bf7d9aSJeff Roberson 	for (word = 0; word < RQB_LEN; word++) {
114522bf7d9aSJeff Roberson 		if (rqb->rqb_bits[word] == 0)
114622bf7d9aSJeff Roberson 			continue;
114722bf7d9aSJeff Roberson 		for (bit = 0; bit < RQB_BPW; bit++) {
1148a2640c9bSPeter Wemm 			if ((rqb->rqb_bits[word] & (1ul << bit)) == 0)
114922bf7d9aSJeff Roberson 				continue;
115022bf7d9aSJeff Roberson 			rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
11519727e637SJeff Roberson 			TAILQ_FOREACH(td, rqh, td_runq)
11529727e637SJeff Roberson 				if (THREAD_CAN_MIGRATE(td) &&
11539727e637SJeff Roberson 				    THREAD_CAN_SCHED(td, cpu))
11549727e637SJeff Roberson 					return (td);
115522bf7d9aSJeff Roberson 		}
115622bf7d9aSJeff Roberson 	}
115722bf7d9aSJeff Roberson 	return (NULL);
115822bf7d9aSJeff Roberson }
115922bf7d9aSJeff Roberson 
1160ae7a6b38SJeff Roberson /*
1161ae7a6b38SJeff Roberson  * Attempt to steal a thread in priority order from a thread queue.
1162ae7a6b38SJeff Roberson  */
11639727e637SJeff Roberson static struct thread *
116462fa74d9SJeff Roberson tdq_steal(struct tdq *tdq, int cpu)
116522bf7d9aSJeff Roberson {
11669727e637SJeff Roberson 	struct thread *td;
116722bf7d9aSJeff Roberson 
1168ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
11699727e637SJeff Roberson 	if ((td = runq_steal(&tdq->tdq_realtime, cpu)) != NULL)
11709727e637SJeff Roberson 		return (td);
11719727e637SJeff Roberson 	if ((td = runq_steal_from(&tdq->tdq_timeshare,
11729727e637SJeff Roberson 	    cpu, tdq->tdq_ridx)) != NULL)
11739727e637SJeff Roberson 		return (td);
117462fa74d9SJeff Roberson 	return (runq_steal(&tdq->tdq_idle, cpu));
117522bf7d9aSJeff Roberson }
117680f86c9fSJeff Roberson 
1177ae7a6b38SJeff Roberson /*
1178ae7a6b38SJeff Roberson  * Sets the thread lock and ts_cpu to match the requested cpu.  Unlocks the
11797fcf154aSJeff Roberson  * current lock and returns with the assigned queue locked.
1180ae7a6b38SJeff Roberson  */
1181ae7a6b38SJeff Roberson static inline struct tdq *
11829727e637SJeff Roberson sched_setcpu(struct thread *td, int cpu, int flags)
118380f86c9fSJeff Roberson {
11849727e637SJeff Roberson 
1185ae7a6b38SJeff Roberson 	struct tdq *tdq;
118661a74c5cSJeff Roberson 	struct mtx *mtx;
118780f86c9fSJeff Roberson 
11889727e637SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1189ae7a6b38SJeff Roberson 	tdq = TDQ_CPU(cpu);
119093ccd6bfSKonstantin Belousov 	td_get_sched(td)->ts_cpu = cpu;
11919727e637SJeff Roberson 	/*
11929727e637SJeff Roberson 	 * If the lock matches just return the queue.
11939727e637SJeff Roberson 	 */
119461a74c5cSJeff Roberson 	if (td->td_lock == TDQ_LOCKPTR(tdq)) {
119561a74c5cSJeff Roberson 		KASSERT((flags & SRQ_HOLD) == 0,
119661a74c5cSJeff Roberson 		    ("sched_setcpu: Invalid lock for SRQ_HOLD"));
1197ae7a6b38SJeff Roberson 		return (tdq);
1198ae7a6b38SJeff Roberson 	}
119961a74c5cSJeff Roberson 
120080f86c9fSJeff Roberson 	/*
1201ae7a6b38SJeff Roberson 	 * The hard case, migration, we need to block the thread first to
1202ae7a6b38SJeff Roberson 	 * prevent order reversals with other cpus locks.
12037b8bfa0dSJeff Roberson 	 */
1204b0b9dee5SAttilio Rao 	spinlock_enter();
120561a74c5cSJeff Roberson 	mtx = thread_lock_block(td);
120661a74c5cSJeff Roberson 	if ((flags & SRQ_HOLD) == 0)
120761a74c5cSJeff Roberson 		mtx_unlock_spin(mtx);
1208ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
1209ae7a6b38SJeff Roberson 	thread_lock_unblock(td, TDQ_LOCKPTR(tdq));
1210b0b9dee5SAttilio Rao 	spinlock_exit();
1211ae7a6b38SJeff Roberson 	return (tdq);
121280f86c9fSJeff Roberson }
12132454aaf5SJeff Roberson 
12148df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_intrbind, "Soft interrupt binding");
12158df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_idle_affinity, "Picked idle cpu based on affinity");
12168df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_affinity, "Picked cpu based on affinity");
12178df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_lowest, "Selected lowest load");
12188df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_local, "Migrated to current cpu");
12198df78c41SJeff Roberson SCHED_STAT_DEFINE(pickcpu_migration, "Selection may have caused migration");
12208df78c41SJeff Roberson 
1221ae7a6b38SJeff Roberson static int
12229727e637SJeff Roberson sched_pickcpu(struct thread *td, int flags)
1223ae7a6b38SJeff Roberson {
122436acfc65SAlexander Motin 	struct cpu_group *cg, *ccg;
12259727e637SJeff Roberson 	struct td_sched *ts;
1226ae7a6b38SJeff Roberson 	struct tdq *tdq;
1227aefe0a8cSAlexander Motin 	cpuset_t *mask;
1228c9205e35SAlexander Motin 	int cpu, pri, self, intr;
12297b8bfa0dSJeff Roberson 
123062fa74d9SJeff Roberson 	self = PCPU_GET(cpuid);
123193ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
1232efe67753SNathan Whitehorn 	KASSERT(!CPU_ABSENT(ts->ts_cpu), ("sched_pickcpu: Start scheduler on "
1233efe67753SNathan Whitehorn 	    "absent CPU %d for thread %s.", ts->ts_cpu, td->td_name));
12347b8bfa0dSJeff Roberson 	if (smp_started == 0)
12357b8bfa0dSJeff Roberson 		return (self);
123628994a58SJeff Roberson 	/*
123728994a58SJeff Roberson 	 * Don't migrate a running thread from sched_switch().
123828994a58SJeff Roberson 	 */
123962fa74d9SJeff Roberson 	if ((flags & SRQ_OURSELF) || !THREAD_CAN_MIGRATE(td))
124062fa74d9SJeff Roberson 		return (ts->ts_cpu);
12417b8bfa0dSJeff Roberson 	/*
124262fa74d9SJeff Roberson 	 * Prefer to run interrupt threads on the processors that generate
124362fa74d9SJeff Roberson 	 * the interrupt.
12447b8bfa0dSJeff Roberson 	 */
124562fa74d9SJeff Roberson 	if (td->td_priority <= PRI_MAX_ITHD && THREAD_CAN_SCHED(td, self) &&
1246c9205e35SAlexander Motin 	    curthread->td_intr_nesting_level) {
1247c55dc51cSAlexander Motin 		tdq = TDQ_SELF();
1248c55dc51cSAlexander Motin 		if (tdq->tdq_lowpri >= PRI_MIN_IDLE) {
1249c55dc51cSAlexander Motin 			SCHED_STAT_INC(pickcpu_idle_affinity);
1250c55dc51cSAlexander Motin 			return (self);
1251c55dc51cSAlexander Motin 		}
125262fa74d9SJeff Roberson 		ts->ts_cpu = self;
1253c9205e35SAlexander Motin 		intr = 1;
1254c55dc51cSAlexander Motin 		cg = tdq->tdq_cg;
1255c55dc51cSAlexander Motin 		goto llc;
1256c55dc51cSAlexander Motin 	} else {
1257c9205e35SAlexander Motin 		intr = 0;
1258c55dc51cSAlexander Motin 		tdq = TDQ_CPU(ts->ts_cpu);
1259c55dc51cSAlexander Motin 		cg = tdq->tdq_cg;
1260c55dc51cSAlexander Motin 	}
12617b8bfa0dSJeff Roberson 	/*
126236acfc65SAlexander Motin 	 * If the thread can run on the last cpu and the affinity has not
12630127914cSEric van Gyzen 	 * expired and it is idle, run it there.
12647b8bfa0dSJeff Roberson 	 */
126536acfc65SAlexander Motin 	if (THREAD_CAN_SCHED(td, ts->ts_cpu) &&
126636acfc65SAlexander Motin 	    tdq->tdq_lowpri >= PRI_MIN_IDLE &&
126736acfc65SAlexander Motin 	    SCHED_AFFINITY(ts, CG_SHARE_L2)) {
1268c55dc51cSAlexander Motin 		if (cg->cg_flags & CG_FLAG_THREAD) {
1269176dd236SAlexander Motin 			/* Check all SMT threads for being idle. */
1270aefe0a8cSAlexander Motin 			for (cpu = cg->cg_first; cpu <= cg->cg_last; cpu++) {
1271176dd236SAlexander Motin 				if (CPU_ISSET(cpu, &cg->cg_mask) &&
1272176dd236SAlexander Motin 				    TDQ_CPU(cpu)->tdq_lowpri < PRI_MIN_IDLE)
127362fa74d9SJeff Roberson 					break;
1274aefe0a8cSAlexander Motin 			}
1275aefe0a8cSAlexander Motin 			if (cpu > cg->cg_last) {
1276176dd236SAlexander Motin 				SCHED_STAT_INC(pickcpu_idle_affinity);
1277176dd236SAlexander Motin 				return (ts->ts_cpu);
127836acfc65SAlexander Motin 			}
1279176dd236SAlexander Motin 		} else {
128036acfc65SAlexander Motin 			SCHED_STAT_INC(pickcpu_idle_affinity);
128136acfc65SAlexander Motin 			return (ts->ts_cpu);
128236acfc65SAlexander Motin 		}
128336acfc65SAlexander Motin 	}
1284c55dc51cSAlexander Motin llc:
128536acfc65SAlexander Motin 	/*
128636acfc65SAlexander Motin 	 * Search for the last level cache CPU group in the tree.
1287c9205e35SAlexander Motin 	 * Skip SMT, identical groups and caches with expired affinity.
1288c9205e35SAlexander Motin 	 * Interrupt threads affinity is explicit and never expires.
128936acfc65SAlexander Motin 	 */
129036acfc65SAlexander Motin 	for (ccg = NULL; cg != NULL; cg = cg->cg_parent) {
129136acfc65SAlexander Motin 		if (cg->cg_flags & CG_FLAG_THREAD)
129236acfc65SAlexander Motin 			continue;
1293c9205e35SAlexander Motin 		if (cg->cg_children == 1 || cg->cg_count == 1)
1294c9205e35SAlexander Motin 			continue;
1295c9205e35SAlexander Motin 		if (cg->cg_level == CG_SHARE_NONE ||
1296c9205e35SAlexander Motin 		    (!intr && !SCHED_AFFINITY(ts, cg->cg_level)))
129736acfc65SAlexander Motin 			continue;
129836acfc65SAlexander Motin 		ccg = cg;
129936acfc65SAlexander Motin 	}
1300c9205e35SAlexander Motin 	/* Found LLC shared by all CPUs, so do a global search. */
1301c9205e35SAlexander Motin 	if (ccg == cpu_top)
1302c9205e35SAlexander Motin 		ccg = NULL;
130362fa74d9SJeff Roberson 	cpu = -1;
1304aefe0a8cSAlexander Motin 	mask = &td->td_cpuset->cs_mask;
1305c9205e35SAlexander Motin 	pri = td->td_priority;
1306c9205e35SAlexander Motin 	/*
1307c9205e35SAlexander Motin 	 * Try hard to keep interrupts within found LLC.  Search the LLC for
1308c9205e35SAlexander Motin 	 * the least loaded CPU we can run now.  For NUMA systems it should
1309c9205e35SAlexander Motin 	 * be within target domain, and it also reduces scheduling overhead.
1310c9205e35SAlexander Motin 	 */
1311c9205e35SAlexander Motin 	if (ccg != NULL && intr) {
1312c9205e35SAlexander Motin 		cpu = sched_lowest(ccg, mask, pri, INT_MAX, ts->ts_cpu);
1313c9205e35SAlexander Motin 		if (cpu >= 0)
1314c9205e35SAlexander Motin 			SCHED_STAT_INC(pickcpu_intrbind);
1315c9205e35SAlexander Motin 	} else
1316c9205e35SAlexander Motin 	/* Search the LLC for the least loaded idle CPU we can run now. */
1317c9205e35SAlexander Motin 	if (ccg != NULL) {
1318c9205e35SAlexander Motin 		cpu = sched_lowest(ccg, mask, max(pri, PRI_MAX_TIMESHARE),
131936acfc65SAlexander Motin 		    INT_MAX, ts->ts_cpu);
1320c9205e35SAlexander Motin 		if (cpu >= 0)
1321c9205e35SAlexander Motin 			SCHED_STAT_INC(pickcpu_affinity);
1322c9205e35SAlexander Motin 	}
1323c9205e35SAlexander Motin 	/* Search globally for the least loaded CPU we can run now. */
1324c9205e35SAlexander Motin 	if (cpu < 0) {
132536acfc65SAlexander Motin 		cpu = sched_lowest(cpu_top, mask, pri, INT_MAX, ts->ts_cpu);
1326c9205e35SAlexander Motin 		if (cpu >= 0)
1327c9205e35SAlexander Motin 			SCHED_STAT_INC(pickcpu_lowest);
1328c9205e35SAlexander Motin 	}
1329c9205e35SAlexander Motin 	/* Search globally for the least loaded CPU. */
1330c9205e35SAlexander Motin 	if (cpu < 0) {
133136acfc65SAlexander Motin 		cpu = sched_lowest(cpu_top, mask, -1, INT_MAX, ts->ts_cpu);
1332c9205e35SAlexander Motin 		if (cpu >= 0)
1333c9205e35SAlexander Motin 			SCHED_STAT_INC(pickcpu_lowest);
1334c9205e35SAlexander Motin 	}
1335bb3dfc6aSAlexander Motin 	KASSERT(cpu >= 0, ("sched_pickcpu: Failed to find a cpu."));
1336efe67753SNathan Whitehorn 	KASSERT(!CPU_ABSENT(cpu), ("sched_pickcpu: Picked absent CPU %d.", cpu));
133762fa74d9SJeff Roberson 	/*
133862fa74d9SJeff Roberson 	 * Compare the lowest loaded cpu to current cpu.
133962fa74d9SJeff Roberson 	 */
1340018ff686SJeff Roberson 	tdq = TDQ_CPU(cpu);
1341018ff686SJeff Roberson 	if (THREAD_CAN_SCHED(td, self) && TDQ_SELF()->tdq_lowpri > pri &&
1342018ff686SJeff Roberson 	    tdq->tdq_lowpri < PRI_MIN_IDLE &&
1343018ff686SJeff Roberson 	    TDQ_SELF()->tdq_load <= tdq->tdq_load + 1) {
13448df78c41SJeff Roberson 		SCHED_STAT_INC(pickcpu_local);
134562fa74d9SJeff Roberson 		cpu = self;
1346c9205e35SAlexander Motin 	}
13478df78c41SJeff Roberson 	if (cpu != ts->ts_cpu)
13488df78c41SJeff Roberson 		SCHED_STAT_INC(pickcpu_migration);
1349ae7a6b38SJeff Roberson 	return (cpu);
135080f86c9fSJeff Roberson }
135162fa74d9SJeff Roberson #endif
135222bf7d9aSJeff Roberson 
135322bf7d9aSJeff Roberson /*
135422bf7d9aSJeff Roberson  * Pick the highest priority task we have and return it.
13550c0a98b2SJeff Roberson  */
13569727e637SJeff Roberson static struct thread *
1357ad1e7d28SJulian Elischer tdq_choose(struct tdq *tdq)
13585d7ef00cSJeff Roberson {
13599727e637SJeff Roberson 	struct thread *td;
13605d7ef00cSJeff Roberson 
1361ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
13629727e637SJeff Roberson 	td = runq_choose(&tdq->tdq_realtime);
13639727e637SJeff Roberson 	if (td != NULL)
13649727e637SJeff Roberson 		return (td);
13659727e637SJeff Roberson 	td = runq_choose_from(&tdq->tdq_timeshare, tdq->tdq_ridx);
13669727e637SJeff Roberson 	if (td != NULL) {
136712d56c0fSJohn Baldwin 		KASSERT(td->td_priority >= PRI_MIN_BATCH,
1368e7d50326SJeff Roberson 		    ("tdq_choose: Invalid priority on timeshare queue %d",
13699727e637SJeff Roberson 		    td->td_priority));
13709727e637SJeff Roberson 		return (td);
137115dc847eSJeff Roberson 	}
13729727e637SJeff Roberson 	td = runq_choose(&tdq->tdq_idle);
13739727e637SJeff Roberson 	if (td != NULL) {
13749727e637SJeff Roberson 		KASSERT(td->td_priority >= PRI_MIN_IDLE,
1375e7d50326SJeff Roberson 		    ("tdq_choose: Invalid priority on idle queue %d",
13769727e637SJeff Roberson 		    td->td_priority));
13779727e637SJeff Roberson 		return (td);
1378e7d50326SJeff Roberson 	}
1379e7d50326SJeff Roberson 
1380e7d50326SJeff Roberson 	return (NULL);
1381245f3abfSJeff Roberson }
13820a016a05SJeff Roberson 
1383ae7a6b38SJeff Roberson /*
1384ae7a6b38SJeff Roberson  * Initialize a thread queue.
1385ae7a6b38SJeff Roberson  */
13860a016a05SJeff Roberson static void
1387018ff686SJeff Roberson tdq_setup(struct tdq *tdq, int id)
13880a016a05SJeff Roberson {
1389ae7a6b38SJeff Roberson 
1390c47f202bSJeff Roberson 	if (bootverbose)
1391018ff686SJeff Roberson 		printf("ULE: setup cpu %d\n", id);
1392e7d50326SJeff Roberson 	runq_init(&tdq->tdq_realtime);
1393e7d50326SJeff Roberson 	runq_init(&tdq->tdq_timeshare);
1394d2ad694cSJeff Roberson 	runq_init(&tdq->tdq_idle);
1395018ff686SJeff Roberson 	tdq->tdq_id = id;
139662fa74d9SJeff Roberson 	snprintf(tdq->tdq_name, sizeof(tdq->tdq_name),
139762fa74d9SJeff Roberson 	    "sched lock %d", (int)TDQ_ID(tdq));
139861a74c5cSJeff Roberson 	mtx_init(&tdq->tdq_lock, tdq->tdq_name, "sched lock", MTX_SPIN);
13998f51ad55SJeff Roberson #ifdef KTR
14008f51ad55SJeff Roberson 	snprintf(tdq->tdq_loadname, sizeof(tdq->tdq_loadname),
14018f51ad55SJeff Roberson 	    "CPU %d load", (int)TDQ_ID(tdq));
14028f51ad55SJeff Roberson #endif
14030a016a05SJeff Roberson }
14040a016a05SJeff Roberson 
1405c47f202bSJeff Roberson #ifdef SMP
1406c47f202bSJeff Roberson static void
1407c47f202bSJeff Roberson sched_setup_smp(void)
1408c47f202bSJeff Roberson {
1409c47f202bSJeff Roberson 	struct tdq *tdq;
1410c47f202bSJeff Roberson 	int i;
1411c47f202bSJeff Roberson 
141262fa74d9SJeff Roberson 	cpu_top = smp_topo();
14133aa6d94eSJohn Baldwin 	CPU_FOREACH(i) {
1414018ff686SJeff Roberson 		tdq = DPCPU_ID_PTR(i, tdq);
1415018ff686SJeff Roberson 		tdq_setup(tdq, i);
141662fa74d9SJeff Roberson 		tdq->tdq_cg = smp_topo_find(cpu_top, i);
141762fa74d9SJeff Roberson 		if (tdq->tdq_cg == NULL)
141862fa74d9SJeff Roberson 			panic("Can't find cpu group for %d\n", i);
1419c47f202bSJeff Roberson 	}
1420018ff686SJeff Roberson 	PCPU_SET(sched, DPCPU_PTR(tdq));
142162fa74d9SJeff Roberson 	balance_tdq = TDQ_SELF();
1422c47f202bSJeff Roberson }
1423c47f202bSJeff Roberson #endif
1424c47f202bSJeff Roberson 
1425ae7a6b38SJeff Roberson /*
1426ae7a6b38SJeff Roberson  * Setup the thread queues and initialize the topology based on MD
1427ae7a6b38SJeff Roberson  * information.
1428ae7a6b38SJeff Roberson  */
142935e6168fSJeff Roberson static void
143035e6168fSJeff Roberson sched_setup(void *dummy)
143135e6168fSJeff Roberson {
1432ae7a6b38SJeff Roberson 	struct tdq *tdq;
1433c47f202bSJeff Roberson 
14340ec896fdSJeff Roberson #ifdef SMP
1435c47f202bSJeff Roberson 	sched_setup_smp();
1436749d01b0SJeff Roberson #else
1437018ff686SJeff Roberson 	tdq_setup(TDQ_SELF(), 0);
1438356500a3SJeff Roberson #endif
1439018ff686SJeff Roberson 	tdq = TDQ_SELF();
1440ae7a6b38SJeff Roberson 
1441ae7a6b38SJeff Roberson 	/* Add thread0's load since it's running. */
1442ae7a6b38SJeff Roberson 	TDQ_LOCK(tdq);
1443e1504695SJeff Roberson 	thread0.td_lock = TDQ_LOCKPTR(tdq);
14449727e637SJeff Roberson 	tdq_load_add(tdq, &thread0);
144562fa74d9SJeff Roberson 	tdq->tdq_lowpri = thread0.td_priority;
1446ae7a6b38SJeff Roberson 	TDQ_UNLOCK(tdq);
144735e6168fSJeff Roberson }
144835e6168fSJeff Roberson 
1449ae7a6b38SJeff Roberson /*
1450579895dfSAlexander Motin  * This routine determines time constants after stathz and hz are setup.
1451ae7a6b38SJeff Roberson  */
1452a1d4fe69SDavid Xu /* ARGSUSED */
1453a1d4fe69SDavid Xu static void
1454a1d4fe69SDavid Xu sched_initticks(void *dummy)
1455a1d4fe69SDavid Xu {
1456ae7a6b38SJeff Roberson 	int incr;
1457ae7a6b38SJeff Roberson 
1458a1d4fe69SDavid Xu 	realstathz = stathz ? stathz : hz;
14595e5c3873SJeff Roberson 	sched_slice = realstathz / SCHED_SLICE_DEFAULT_DIVISOR;
14605e5c3873SJeff Roberson 	sched_slice_min = sched_slice / SCHED_SLICE_MIN_DIVISOR;
146137f4e025SAlexander Motin 	hogticks = imax(1, (2 * hz * sched_slice + realstathz / 2) /
146237f4e025SAlexander Motin 	    realstathz);
1463a1d4fe69SDavid Xu 
1464a1d4fe69SDavid Xu 	/*
1465e7d50326SJeff Roberson 	 * tickincr is shifted out by 10 to avoid rounding errors due to
14663f872f85SJeff Roberson 	 * hz not being evenly divisible by stathz on all platforms.
1467e7d50326SJeff Roberson 	 */
1468ae7a6b38SJeff Roberson 	incr = (hz << SCHED_TICK_SHIFT) / realstathz;
1469e7d50326SJeff Roberson 	/*
1470e7d50326SJeff Roberson 	 * This does not work for values of stathz that are more than
1471e7d50326SJeff Roberson 	 * 1 << SCHED_TICK_SHIFT * hz.  In practice this does not happen.
1472a1d4fe69SDavid Xu 	 */
1473ae7a6b38SJeff Roberson 	if (incr == 0)
1474ae7a6b38SJeff Roberson 		incr = 1;
1475ae7a6b38SJeff Roberson 	tickincr = incr;
14767b8bfa0dSJeff Roberson #ifdef SMP
14779862717aSJeff Roberson 	/*
14787fcf154aSJeff Roberson 	 * Set the default balance interval now that we know
14797fcf154aSJeff Roberson 	 * what realstathz is.
14807fcf154aSJeff Roberson 	 */
14817fcf154aSJeff Roberson 	balance_interval = realstathz;
1482290d9060SDon Lewis 	balance_ticks = balance_interval;
14837b8bfa0dSJeff Roberson 	affinity = SCHED_AFFINITY_DEFAULT;
14847b8bfa0dSJeff Roberson #endif
1485b3f40a41SAlexander Motin 	if (sched_idlespinthresh < 0)
14862c27cb3aSAlexander Motin 		sched_idlespinthresh = 2 * max(10000, 6 * hz) / realstathz;
1487a1d4fe69SDavid Xu }
1488a1d4fe69SDavid Xu 
148935e6168fSJeff Roberson /*
1490ae7a6b38SJeff Roberson  * This is the core of the interactivity algorithm.  Determines a score based
1491ae7a6b38SJeff Roberson  * on past behavior.  It is the ratio of sleep time to run time scaled to
1492ae7a6b38SJeff Roberson  * a [0, 100] integer.  This is the voluntary sleep time of a process, which
1493ae7a6b38SJeff Roberson  * differs from the cpu usage because it does not account for time spent
1494ae7a6b38SJeff Roberson  * waiting on a run-queue.  Would be prettier if we had floating point.
149557031f79SGeorge V. Neville-Neil  *
149657031f79SGeorge V. Neville-Neil  * When a thread's sleep time is greater than its run time the
149757031f79SGeorge V. Neville-Neil  * calculation is:
149857031f79SGeorge V. Neville-Neil  *
149957031f79SGeorge V. Neville-Neil  *                           scaling factor
150057031f79SGeorge V. Neville-Neil  * interactivity score =  ---------------------
150157031f79SGeorge V. Neville-Neil  *                        sleep time / run time
150257031f79SGeorge V. Neville-Neil  *
150357031f79SGeorge V. Neville-Neil  *
150457031f79SGeorge V. Neville-Neil  * When a thread's run time is greater than its sleep time the
150557031f79SGeorge V. Neville-Neil  * calculation is:
150657031f79SGeorge V. Neville-Neil  *
150757031f79SGeorge V. Neville-Neil  *                                                 scaling factor
150843521b46Swiklam  * interactivity score = 2 * scaling factor  -  ---------------------
150957031f79SGeorge V. Neville-Neil  *                                              run time / sleep time
1510ae7a6b38SJeff Roberson  */
1511ae7a6b38SJeff Roberson static int
1512ae7a6b38SJeff Roberson sched_interact_score(struct thread *td)
1513ae7a6b38SJeff Roberson {
1514ae7a6b38SJeff Roberson 	struct td_sched *ts;
1515ae7a6b38SJeff Roberson 	int div;
1516ae7a6b38SJeff Roberson 
151793ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
1518ae7a6b38SJeff Roberson 	/*
1519ae7a6b38SJeff Roberson 	 * The score is only needed if this is likely to be an interactive
1520ae7a6b38SJeff Roberson 	 * task.  Don't go through the expense of computing it if there's
1521ae7a6b38SJeff Roberson 	 * no chance.
1522ae7a6b38SJeff Roberson 	 */
1523ae7a6b38SJeff Roberson 	if (sched_interact <= SCHED_INTERACT_HALF &&
1524ae7a6b38SJeff Roberson 		ts->ts_runtime >= ts->ts_slptime)
1525ae7a6b38SJeff Roberson 			return (SCHED_INTERACT_HALF);
1526ae7a6b38SJeff Roberson 
1527ae7a6b38SJeff Roberson 	if (ts->ts_runtime > ts->ts_slptime) {
1528ae7a6b38SJeff Roberson 		div = max(1, ts->ts_runtime / SCHED_INTERACT_HALF);
1529ae7a6b38SJeff Roberson 		return (SCHED_INTERACT_HALF +
1530ae7a6b38SJeff Roberson 		    (SCHED_INTERACT_HALF - (ts->ts_slptime / div)));
1531ae7a6b38SJeff Roberson 	}
1532ae7a6b38SJeff Roberson 	if (ts->ts_slptime > ts->ts_runtime) {
1533ae7a6b38SJeff Roberson 		div = max(1, ts->ts_slptime / SCHED_INTERACT_HALF);
1534ae7a6b38SJeff Roberson 		return (ts->ts_runtime / div);
1535ae7a6b38SJeff Roberson 	}
1536ae7a6b38SJeff Roberson 	/* runtime == slptime */
1537ae7a6b38SJeff Roberson 	if (ts->ts_runtime)
1538ae7a6b38SJeff Roberson 		return (SCHED_INTERACT_HALF);
1539ae7a6b38SJeff Roberson 
1540ae7a6b38SJeff Roberson 	/*
1541ae7a6b38SJeff Roberson 	 * This can happen if slptime and runtime are 0.
1542ae7a6b38SJeff Roberson 	 */
1543ae7a6b38SJeff Roberson 	return (0);
1544ae7a6b38SJeff Roberson 
1545ae7a6b38SJeff Roberson }
1546ae7a6b38SJeff Roberson 
1547ae7a6b38SJeff Roberson /*
154835e6168fSJeff Roberson  * Scale the scheduling priority according to the "interactivity" of this
154935e6168fSJeff Roberson  * process.
155035e6168fSJeff Roberson  */
155115dc847eSJeff Roberson static void
15528460a577SJohn Birrell sched_priority(struct thread *td)
155335e6168fSJeff Roberson {
1554e7d50326SJeff Roberson 	int score;
155535e6168fSJeff Roberson 	int pri;
155635e6168fSJeff Roberson 
1557c9a8cba4SJohn Baldwin 	if (PRI_BASE(td->td_pri_class) != PRI_TIMESHARE)
155815dc847eSJeff Roberson 		return;
1559e7d50326SJeff Roberson 	/*
1560e7d50326SJeff Roberson 	 * If the score is interactive we place the thread in the realtime
1561e7d50326SJeff Roberson 	 * queue with a priority that is less than kernel and interrupt
1562e7d50326SJeff Roberson 	 * priorities.  These threads are not subject to nice restrictions.
1563e7d50326SJeff Roberson 	 *
1564ae7a6b38SJeff Roberson 	 * Scores greater than this are placed on the normal timeshare queue
1565e7d50326SJeff Roberson 	 * where the priority is partially decided by the most recent cpu
1566e7d50326SJeff Roberson 	 * utilization and the rest is decided by nice value.
1567a5423ea3SJeff Roberson 	 *
1568a5423ea3SJeff Roberson 	 * The nice value of the process has a linear effect on the calculated
1569a5423ea3SJeff Roberson 	 * score.  Negative nice values make it easier for a thread to be
1570a5423ea3SJeff Roberson 	 * considered interactive.
1571e7d50326SJeff Roberson 	 */
1572a0f15352SJohn Baldwin 	score = imax(0, sched_interact_score(td) + td->td_proc->p_nice);
1573e7d50326SJeff Roberson 	if (score < sched_interact) {
157412d56c0fSJohn Baldwin 		pri = PRI_MIN_INTERACT;
157512d56c0fSJohn Baldwin 		pri += ((PRI_MAX_INTERACT - PRI_MIN_INTERACT + 1) /
157678920008SJohn Baldwin 		    sched_interact) * score;
157712d56c0fSJohn Baldwin 		KASSERT(pri >= PRI_MIN_INTERACT && pri <= PRI_MAX_INTERACT,
15789a93305aSJeff Roberson 		    ("sched_priority: invalid interactive priority %d score %d",
15799a93305aSJeff Roberson 		    pri, score));
1580e7d50326SJeff Roberson 	} else {
1581e7d50326SJeff Roberson 		pri = SCHED_PRI_MIN;
158293ccd6bfSKonstantin Belousov 		if (td_get_sched(td)->ts_ticks)
158393ccd6bfSKonstantin Belousov 			pri += min(SCHED_PRI_TICKS(td_get_sched(td)),
15845457fa23SJohn Baldwin 			    SCHED_PRI_RANGE - 1);
1585e7d50326SJeff Roberson 		pri += SCHED_PRI_NICE(td->td_proc->p_nice);
158612d56c0fSJohn Baldwin 		KASSERT(pri >= PRI_MIN_BATCH && pri <= PRI_MAX_BATCH,
1587ae7a6b38SJeff Roberson 		    ("sched_priority: invalid priority %d: nice %d, "
1588ae7a6b38SJeff Roberson 		    "ticks %d ftick %d ltick %d tick pri %d",
158993ccd6bfSKonstantin Belousov 		    pri, td->td_proc->p_nice, td_get_sched(td)->ts_ticks,
159093ccd6bfSKonstantin Belousov 		    td_get_sched(td)->ts_ftick, td_get_sched(td)->ts_ltick,
159193ccd6bfSKonstantin Belousov 		    SCHED_PRI_TICKS(td_get_sched(td))));
1592e7d50326SJeff Roberson 	}
15938460a577SJohn Birrell 	sched_user_prio(td, pri);
159435e6168fSJeff Roberson 
159515dc847eSJeff Roberson 	return;
159635e6168fSJeff Roberson }
159735e6168fSJeff Roberson 
159835e6168fSJeff Roberson /*
1599d322132cSJeff Roberson  * This routine enforces a maximum limit on the amount of scheduling history
1600ae7a6b38SJeff Roberson  * kept.  It is called after either the slptime or runtime is adjusted.  This
1601ae7a6b38SJeff Roberson  * function is ugly due to integer math.
1602d322132cSJeff Roberson  */
16034b60e324SJeff Roberson static void
16048460a577SJohn Birrell sched_interact_update(struct thread *td)
16054b60e324SJeff Roberson {
1606155b6ca1SJeff Roberson 	struct td_sched *ts;
16079a93305aSJeff Roberson 	u_int sum;
16083f741ca1SJeff Roberson 
160993ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
1610ae7a6b38SJeff Roberson 	sum = ts->ts_runtime + ts->ts_slptime;
1611d322132cSJeff Roberson 	if (sum < SCHED_SLP_RUN_MAX)
1612d322132cSJeff Roberson 		return;
1613d322132cSJeff Roberson 	/*
1614155b6ca1SJeff Roberson 	 * This only happens from two places:
1615155b6ca1SJeff Roberson 	 * 1) We have added an unusual amount of run time from fork_exit.
1616155b6ca1SJeff Roberson 	 * 2) We have added an unusual amount of sleep time from sched_sleep().
1617155b6ca1SJeff Roberson 	 */
1618155b6ca1SJeff Roberson 	if (sum > SCHED_SLP_RUN_MAX * 2) {
1619ae7a6b38SJeff Roberson 		if (ts->ts_runtime > ts->ts_slptime) {
1620ae7a6b38SJeff Roberson 			ts->ts_runtime = SCHED_SLP_RUN_MAX;
1621ae7a6b38SJeff Roberson 			ts->ts_slptime = 1;
1622155b6ca1SJeff Roberson 		} else {
1623ae7a6b38SJeff Roberson 			ts->ts_slptime = SCHED_SLP_RUN_MAX;
1624ae7a6b38SJeff Roberson 			ts->ts_runtime = 1;
1625155b6ca1SJeff Roberson 		}
1626155b6ca1SJeff Roberson 		return;
1627155b6ca1SJeff Roberson 	}
1628155b6ca1SJeff Roberson 	/*
1629d322132cSJeff Roberson 	 * If we have exceeded by more than 1/5th then the algorithm below
1630d322132cSJeff Roberson 	 * will not bring us back into range.  Dividing by two here forces
16312454aaf5SJeff Roberson 	 * us into the range of [4/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX]
1632d322132cSJeff Roberson 	 */
163337a35e4aSJeff Roberson 	if (sum > (SCHED_SLP_RUN_MAX / 5) * 6) {
1634ae7a6b38SJeff Roberson 		ts->ts_runtime /= 2;
1635ae7a6b38SJeff Roberson 		ts->ts_slptime /= 2;
1636d322132cSJeff Roberson 		return;
1637d322132cSJeff Roberson 	}
1638ae7a6b38SJeff Roberson 	ts->ts_runtime = (ts->ts_runtime / 5) * 4;
1639ae7a6b38SJeff Roberson 	ts->ts_slptime = (ts->ts_slptime / 5) * 4;
1640d322132cSJeff Roberson }
1641d322132cSJeff Roberson 
1642ae7a6b38SJeff Roberson /*
1643ae7a6b38SJeff Roberson  * Scale back the interactivity history when a child thread is created.  The
1644ae7a6b38SJeff Roberson  * history is inherited from the parent but the thread may behave totally
1645ae7a6b38SJeff Roberson  * differently.  For example, a shell spawning a compiler process.  We want
1646ae7a6b38SJeff Roberson  * to learn that the compiler is behaving badly very quickly.
1647ae7a6b38SJeff Roberson  */
1648d322132cSJeff Roberson static void
16498460a577SJohn Birrell sched_interact_fork(struct thread *td)
1650d322132cSJeff Roberson {
165193ccd6bfSKonstantin Belousov 	struct td_sched *ts;
1652d322132cSJeff Roberson 	int ratio;
1653d322132cSJeff Roberson 	int sum;
1654d322132cSJeff Roberson 
165593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
165693ccd6bfSKonstantin Belousov 	sum = ts->ts_runtime + ts->ts_slptime;
1657d322132cSJeff Roberson 	if (sum > SCHED_SLP_RUN_FORK) {
1658d322132cSJeff Roberson 		ratio = sum / SCHED_SLP_RUN_FORK;
165993ccd6bfSKonstantin Belousov 		ts->ts_runtime /= ratio;
166093ccd6bfSKonstantin Belousov 		ts->ts_slptime /= ratio;
16614b60e324SJeff Roberson 	}
16624b60e324SJeff Roberson }
16634b60e324SJeff Roberson 
166415dc847eSJeff Roberson /*
1665ae7a6b38SJeff Roberson  * Called from proc0_init() to setup the scheduler fields.
1666ed062c8dSJulian Elischer  */
1667ed062c8dSJulian Elischer void
1668ed062c8dSJulian Elischer schedinit(void)
1669ed062c8dSJulian Elischer {
167093ccd6bfSKonstantin Belousov 	struct td_sched *ts0;
1671e7d50326SJeff Roberson 
1672ed062c8dSJulian Elischer 	/*
167393ccd6bfSKonstantin Belousov 	 * Set up the scheduler specific parts of thread0.
1674ed062c8dSJulian Elischer 	 */
167593ccd6bfSKonstantin Belousov 	ts0 = td_get_sched(&thread0);
167693ccd6bfSKonstantin Belousov 	ts0->ts_ltick = ticks;
167793ccd6bfSKonstantin Belousov 	ts0->ts_ftick = ticks;
167893ccd6bfSKonstantin Belousov 	ts0->ts_slice = 0;
16791408b84aSHans Petter Selasky 	ts0->ts_cpu = curcpu;	/* set valid CPU number */
1680ed062c8dSJulian Elischer }
1681ed062c8dSJulian Elischer 
1682ed062c8dSJulian Elischer /*
168315dc847eSJeff Roberson  * This is only somewhat accurate since given many processes of the same
168415dc847eSJeff Roberson  * priority they will switch when their slices run out, which will be
1685e7d50326SJeff Roberson  * at most sched_slice stathz ticks.
168615dc847eSJeff Roberson  */
168735e6168fSJeff Roberson int
168835e6168fSJeff Roberson sched_rr_interval(void)
168935e6168fSJeff Roberson {
1690e7d50326SJeff Roberson 
1691579895dfSAlexander Motin 	/* Convert sched_slice from stathz to hz. */
169237f4e025SAlexander Motin 	return (imax(1, (sched_slice * hz + realstathz / 2) / realstathz));
169335e6168fSJeff Roberson }
169435e6168fSJeff Roberson 
1695ae7a6b38SJeff Roberson /*
1696ae7a6b38SJeff Roberson  * Update the percent cpu tracking information when it is requested or
1697ae7a6b38SJeff Roberson  * the total history exceeds the maximum.  We keep a sliding history of
1698ae7a6b38SJeff Roberson  * tick counts that slowly decays.  This is less precise than the 4BSD
1699ae7a6b38SJeff Roberson  * mechanism since it happens with less regular and frequent events.
1700ae7a6b38SJeff Roberson  */
170122bf7d9aSJeff Roberson static void
17027295465eSAlexander Motin sched_pctcpu_update(struct td_sched *ts, int run)
170335e6168fSJeff Roberson {
17047295465eSAlexander Motin 	int t = ticks;
1705e7d50326SJeff Roberson 
170678133024SMark Johnston 	/*
170778133024SMark Johnston 	 * The signed difference may be negative if the thread hasn't run for
170878133024SMark Johnston 	 * over half of the ticks rollover period.
170978133024SMark Johnston 	 */
171078133024SMark Johnston 	if ((u_int)(t - ts->ts_ltick) >= SCHED_TICK_TARG) {
1711ad1e7d28SJulian Elischer 		ts->ts_ticks = 0;
17127295465eSAlexander Motin 		ts->ts_ftick = t - SCHED_TICK_TARG;
17137295465eSAlexander Motin 	} else if (t - ts->ts_ftick >= SCHED_TICK_MAX) {
17147295465eSAlexander Motin 		ts->ts_ticks = (ts->ts_ticks / (ts->ts_ltick - ts->ts_ftick)) *
17157295465eSAlexander Motin 		    (ts->ts_ltick - (t - SCHED_TICK_TARG));
17167295465eSAlexander Motin 		ts->ts_ftick = t - SCHED_TICK_TARG;
17177295465eSAlexander Motin 	}
17187295465eSAlexander Motin 	if (run)
17197295465eSAlexander Motin 		ts->ts_ticks += (t - ts->ts_ltick) << SCHED_TICK_SHIFT;
17207295465eSAlexander Motin 	ts->ts_ltick = t;
172135e6168fSJeff Roberson }
172235e6168fSJeff Roberson 
1723ae7a6b38SJeff Roberson /*
1724ae7a6b38SJeff Roberson  * Adjust the priority of a thread.  Move it to the appropriate run-queue
1725ae7a6b38SJeff Roberson  * if necessary.  This is the back-end for several priority related
1726ae7a6b38SJeff Roberson  * functions.
1727ae7a6b38SJeff Roberson  */
1728e7d50326SJeff Roberson static void
1729f5c157d9SJohn Baldwin sched_thread_priority(struct thread *td, u_char prio)
173035e6168fSJeff Roberson {
1731ad1e7d28SJulian Elischer 	struct td_sched *ts;
173273daf66fSJeff Roberson 	struct tdq *tdq;
173373daf66fSJeff Roberson 	int oldpri;
173435e6168fSJeff Roberson 
17358f51ad55SJeff Roberson 	KTR_POINT3(KTR_SCHED, "thread", sched_tdname(td), "prio",
17368f51ad55SJeff Roberson 	    "prio:%d", td->td_priority, "new prio:%d", prio,
17378f51ad55SJeff Roberson 	    KTR_ATTR_LINKED, sched_tdname(curthread));
1738d9fae5abSAndriy Gapon 	SDT_PROBE3(sched, , , change__pri, td, td->td_proc, prio);
1739e87fc7cfSAndriy Gapon 	if (td != curthread && prio < td->td_priority) {
17408f51ad55SJeff Roberson 		KTR_POINT3(KTR_SCHED, "thread", sched_tdname(curthread),
17418f51ad55SJeff Roberson 		    "lend prio", "prio:%d", td->td_priority, "new prio:%d",
17428f51ad55SJeff Roberson 		    prio, KTR_ATTR_LINKED, sched_tdname(td));
1743d9fae5abSAndriy Gapon 		SDT_PROBE4(sched, , , lend__pri, td, td->td_proc, prio,
1744b3e9e682SRyan Stone 		    curthread);
17458f51ad55SJeff Roberson 	}
174693ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
17477b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1748f5c157d9SJohn Baldwin 	if (td->td_priority == prio)
1749f5c157d9SJohn Baldwin 		return;
17503f741ca1SJeff Roberson 	/*
17513f741ca1SJeff Roberson 	 * If the priority has been elevated due to priority
17523f741ca1SJeff Roberson 	 * propagation, we may have to move ourselves to a new
1753e7d50326SJeff Roberson 	 * queue.  This could be optimized to not re-add in some
1754e7d50326SJeff Roberson 	 * cases.
1755f2b74cbfSJeff Roberson 	 */
17566d55b3ecSJeff Roberson 	if (TD_ON_RUNQ(td) && prio < td->td_priority) {
1757e7d50326SJeff Roberson 		sched_rem(td);
1758e7d50326SJeff Roberson 		td->td_priority = prio;
175961a74c5cSJeff Roberson 		sched_add(td, SRQ_BORROWING | SRQ_HOLDTD);
176073daf66fSJeff Roberson 		return;
176173daf66fSJeff Roberson 	}
17626d55b3ecSJeff Roberson 	/*
17636d55b3ecSJeff Roberson 	 * If the thread is currently running we may have to adjust the lowpri
17646d55b3ecSJeff Roberson 	 * information so other cpus are aware of our current priority.
17656d55b3ecSJeff Roberson 	 */
17666d55b3ecSJeff Roberson 	if (TD_IS_RUNNING(td)) {
1767ae7a6b38SJeff Roberson 		tdq = TDQ_CPU(ts->ts_cpu);
176862fa74d9SJeff Roberson 		oldpri = td->td_priority;
17693f741ca1SJeff Roberson 		td->td_priority = prio;
177062fa74d9SJeff Roberson 		if (prio < tdq->tdq_lowpri)
177162fa74d9SJeff Roberson 			tdq->tdq_lowpri = prio;
177262fa74d9SJeff Roberson 		else if (tdq->tdq_lowpri == oldpri)
177362fa74d9SJeff Roberson 			tdq_setlowpri(tdq, td);
17746d55b3ecSJeff Roberson 		return;
177573daf66fSJeff Roberson 	}
17766d55b3ecSJeff Roberson 	td->td_priority = prio;
1777ae7a6b38SJeff Roberson }
177835e6168fSJeff Roberson 
1779f5c157d9SJohn Baldwin /*
1780f5c157d9SJohn Baldwin  * Update a thread's priority when it is lent another thread's
1781f5c157d9SJohn Baldwin  * priority.
1782f5c157d9SJohn Baldwin  */
1783f5c157d9SJohn Baldwin void
1784f5c157d9SJohn Baldwin sched_lend_prio(struct thread *td, u_char prio)
1785f5c157d9SJohn Baldwin {
1786f5c157d9SJohn Baldwin 
1787f5c157d9SJohn Baldwin 	td->td_flags |= TDF_BORROWING;
1788f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1789f5c157d9SJohn Baldwin }
1790f5c157d9SJohn Baldwin 
1791f5c157d9SJohn Baldwin /*
1792f5c157d9SJohn Baldwin  * Restore a thread's priority when priority propagation is
1793f5c157d9SJohn Baldwin  * over.  The prio argument is the minimum priority the thread
1794f5c157d9SJohn Baldwin  * needs to have to satisfy other possible priority lending
1795f5c157d9SJohn Baldwin  * requests.  If the thread's regular priority is less
1796f5c157d9SJohn Baldwin  * important than prio, the thread will keep a priority boost
1797f5c157d9SJohn Baldwin  * of prio.
1798f5c157d9SJohn Baldwin  */
1799f5c157d9SJohn Baldwin void
1800f5c157d9SJohn Baldwin sched_unlend_prio(struct thread *td, u_char prio)
1801f5c157d9SJohn Baldwin {
1802f5c157d9SJohn Baldwin 	u_char base_pri;
1803f5c157d9SJohn Baldwin 
1804f5c157d9SJohn Baldwin 	if (td->td_base_pri >= PRI_MIN_TIMESHARE &&
1805f5c157d9SJohn Baldwin 	    td->td_base_pri <= PRI_MAX_TIMESHARE)
18068460a577SJohn Birrell 		base_pri = td->td_user_pri;
1807f5c157d9SJohn Baldwin 	else
1808f5c157d9SJohn Baldwin 		base_pri = td->td_base_pri;
1809f5c157d9SJohn Baldwin 	if (prio >= base_pri) {
1810f5c157d9SJohn Baldwin 		td->td_flags &= ~TDF_BORROWING;
1811f5c157d9SJohn Baldwin 		sched_thread_priority(td, base_pri);
1812f5c157d9SJohn Baldwin 	} else
1813f5c157d9SJohn Baldwin 		sched_lend_prio(td, prio);
1814f5c157d9SJohn Baldwin }
1815f5c157d9SJohn Baldwin 
1816ae7a6b38SJeff Roberson /*
1817ae7a6b38SJeff Roberson  * Standard entry for setting the priority to an absolute value.
1818ae7a6b38SJeff Roberson  */
1819f5c157d9SJohn Baldwin void
1820f5c157d9SJohn Baldwin sched_prio(struct thread *td, u_char prio)
1821f5c157d9SJohn Baldwin {
1822f5c157d9SJohn Baldwin 	u_char oldprio;
1823f5c157d9SJohn Baldwin 
1824f5c157d9SJohn Baldwin 	/* First, update the base priority. */
1825f5c157d9SJohn Baldwin 	td->td_base_pri = prio;
1826f5c157d9SJohn Baldwin 
1827f5c157d9SJohn Baldwin 	/*
182850aaa791SJohn Baldwin 	 * If the thread is borrowing another thread's priority, don't
1829f5c157d9SJohn Baldwin 	 * ever lower the priority.
1830f5c157d9SJohn Baldwin 	 */
1831f5c157d9SJohn Baldwin 	if (td->td_flags & TDF_BORROWING && td->td_priority < prio)
1832f5c157d9SJohn Baldwin 		return;
1833f5c157d9SJohn Baldwin 
1834f5c157d9SJohn Baldwin 	/* Change the real priority. */
1835f5c157d9SJohn Baldwin 	oldprio = td->td_priority;
1836f5c157d9SJohn Baldwin 	sched_thread_priority(td, prio);
1837f5c157d9SJohn Baldwin 
1838f5c157d9SJohn Baldwin 	/*
1839f5c157d9SJohn Baldwin 	 * If the thread is on a turnstile, then let the turnstile update
1840f5c157d9SJohn Baldwin 	 * its state.
1841f5c157d9SJohn Baldwin 	 */
1842f5c157d9SJohn Baldwin 	if (TD_ON_LOCK(td) && oldprio != prio)
1843f5c157d9SJohn Baldwin 		turnstile_adjust(td, oldprio);
1844f5c157d9SJohn Baldwin }
1845f5c157d9SJohn Baldwin 
1846ae7a6b38SJeff Roberson /*
1847ae7a6b38SJeff Roberson  * Set the base user priority, does not effect current running priority.
1848ae7a6b38SJeff Roberson  */
184935e6168fSJeff Roberson void
18508460a577SJohn Birrell sched_user_prio(struct thread *td, u_char prio)
18513db720fdSDavid Xu {
18523db720fdSDavid Xu 
18538460a577SJohn Birrell 	td->td_base_user_pri = prio;
1854acbe332aSDavid Xu 	if (td->td_lend_user_pri <= prio)
1855fc6c30f6SJulian Elischer 		return;
18568460a577SJohn Birrell 	td->td_user_pri = prio;
18573db720fdSDavid Xu }
18583db720fdSDavid Xu 
18593db720fdSDavid Xu void
18603db720fdSDavid Xu sched_lend_user_prio(struct thread *td, u_char prio)
18613db720fdSDavid Xu {
18623db720fdSDavid Xu 
1863435806d3SDavid Xu 	THREAD_LOCK_ASSERT(td, MA_OWNED);
1864acbe332aSDavid Xu 	td->td_lend_user_pri = prio;
1865c8e368a9SDavid Xu 	td->td_user_pri = min(prio, td->td_base_user_pri);
1866c8e368a9SDavid Xu 	if (td->td_priority > td->td_user_pri)
1867c8e368a9SDavid Xu 		sched_prio(td, td->td_user_pri);
1868c8e368a9SDavid Xu 	else if (td->td_priority != td->td_user_pri)
1869c8e368a9SDavid Xu 		td->td_flags |= TDF_NEEDRESCHED;
1870435806d3SDavid Xu }
18713db720fdSDavid Xu 
1872ac97da9aSMateusz Guzik /*
1873ac97da9aSMateusz Guzik  * Like the above but first check if there is anything to do.
1874ac97da9aSMateusz Guzik  */
1875ac97da9aSMateusz Guzik void
1876ac97da9aSMateusz Guzik sched_lend_user_prio_cond(struct thread *td, u_char prio)
1877ac97da9aSMateusz Guzik {
1878ac97da9aSMateusz Guzik 
1879ac97da9aSMateusz Guzik 	if (td->td_lend_user_pri != prio)
1880ac97da9aSMateusz Guzik 		goto lend;
1881ac97da9aSMateusz Guzik 	if (td->td_user_pri != min(prio, td->td_base_user_pri))
1882ac97da9aSMateusz Guzik 		goto lend;
1883b77594bbSMateusz Guzik 	if (td->td_priority != td->td_user_pri)
1884ac97da9aSMateusz Guzik 		goto lend;
1885ac97da9aSMateusz Guzik 	return;
1886ac97da9aSMateusz Guzik 
1887ac97da9aSMateusz Guzik lend:
1888ac97da9aSMateusz Guzik 	thread_lock(td);
1889ac97da9aSMateusz Guzik 	sched_lend_user_prio(td, prio);
1890ac97da9aSMateusz Guzik 	thread_unlock(td);
1891ac97da9aSMateusz Guzik }
1892ac97da9aSMateusz Guzik 
18934c8a8cfcSKonstantin Belousov #ifdef SMP
1894ae7a6b38SJeff Roberson /*
189597e9382dSDon Lewis  * This tdq is about to idle.  Try to steal a thread from another CPU before
189697e9382dSDon Lewis  * choosing the idle thread.
189797e9382dSDon Lewis  */
189897e9382dSDon Lewis static void
189997e9382dSDon Lewis tdq_trysteal(struct tdq *tdq)
190097e9382dSDon Lewis {
19012668bb2aSAlexander Motin 	struct cpu_group *cg, *parent;
190297e9382dSDon Lewis 	struct tdq *steal;
190397e9382dSDon Lewis 	cpuset_t mask;
19042668bb2aSAlexander Motin 	int cpu, i, goup;
190597e9382dSDon Lewis 
190697e9382dSDon Lewis 	if (smp_started == 0 || trysteal_limit == 0 || tdq->tdq_cg == NULL)
190797e9382dSDon Lewis 		return;
190897e9382dSDon Lewis 	CPU_FILL(&mask);
190997e9382dSDon Lewis 	CPU_CLR(PCPU_GET(cpuid), &mask);
191097e9382dSDon Lewis 	/* We don't want to be preempted while we're iterating. */
191197e9382dSDon Lewis 	spinlock_enter();
191297e9382dSDon Lewis 	TDQ_UNLOCK(tdq);
19132668bb2aSAlexander Motin 	for (i = 1, cg = tdq->tdq_cg, goup = 0; ; ) {
1914aefe0a8cSAlexander Motin 		cpu = sched_highest(cg, &mask, steal_thresh);
191597e9382dSDon Lewis 		/*
191697e9382dSDon Lewis 		 * If a thread was added while interrupts were disabled don't
191797e9382dSDon Lewis 		 * steal one here.
191897e9382dSDon Lewis 		 */
191997e9382dSDon Lewis 		if (tdq->tdq_load > 0) {
192097e9382dSDon Lewis 			TDQ_LOCK(tdq);
192197e9382dSDon Lewis 			break;
192297e9382dSDon Lewis 		}
19232668bb2aSAlexander Motin 
19242668bb2aSAlexander Motin 		/*
19252668bb2aSAlexander Motin 		 * We found no CPU to steal from in this group.  Escalate to
19262668bb2aSAlexander Motin 		 * the parent and repeat.  But if parent has only two children
19272668bb2aSAlexander Motin 		 * groups we can avoid searching this group again by searching
19282668bb2aSAlexander Motin 		 * the other one specifically and then escalating two levels.
19292668bb2aSAlexander Motin 		 */
193097e9382dSDon Lewis 		if (cpu == -1) {
19312668bb2aSAlexander Motin 			if (goup) {
193297e9382dSDon Lewis 				cg = cg->cg_parent;
19332668bb2aSAlexander Motin 				goup = 0;
19342668bb2aSAlexander Motin 			}
19352668bb2aSAlexander Motin 			if (++i > trysteal_limit) {
193697e9382dSDon Lewis 				TDQ_LOCK(tdq);
193797e9382dSDon Lewis 				break;
193897e9382dSDon Lewis 			}
19392668bb2aSAlexander Motin 			parent = cg->cg_parent;
19402668bb2aSAlexander Motin 			if (parent == NULL) {
19412668bb2aSAlexander Motin 				TDQ_LOCK(tdq);
19422668bb2aSAlexander Motin 				break;
19432668bb2aSAlexander Motin 			}
19442668bb2aSAlexander Motin 			if (parent->cg_children == 2) {
19452668bb2aSAlexander Motin 				if (cg == &parent->cg_child[0])
19462668bb2aSAlexander Motin 					cg = &parent->cg_child[1];
19472668bb2aSAlexander Motin 				else
19482668bb2aSAlexander Motin 					cg = &parent->cg_child[0];
19492668bb2aSAlexander Motin 				goup = 1;
19502668bb2aSAlexander Motin 			} else
19512668bb2aSAlexander Motin 				cg = parent;
195297e9382dSDon Lewis 			continue;
195397e9382dSDon Lewis 		}
195497e9382dSDon Lewis 		steal = TDQ_CPU(cpu);
195597e9382dSDon Lewis 		/*
195697e9382dSDon Lewis 		 * The data returned by sched_highest() is stale and
195797e9382dSDon Lewis                  * the chosen CPU no longer has an eligible thread.
195897e9382dSDon Lewis 		 */
195997e9382dSDon Lewis 		if (steal->tdq_load < steal_thresh ||
196097e9382dSDon Lewis 		    steal->tdq_transferable == 0)
196197e9382dSDon Lewis 			continue;
196297e9382dSDon Lewis 		/*
1963*8bb173fbSAlexander Motin 		 * Try to lock both queues. If we are assigned a thread while
1964*8bb173fbSAlexander Motin 		 * waited for the lock, switch to it now instead of stealing.
1965*8bb173fbSAlexander Motin 		 * If we can't get the lock, then somebody likely got there
1966*8bb173fbSAlexander Motin 		 * first.  At this point unconditonally exit the loop to
1967*8bb173fbSAlexander Motin 		 * bound the time spent in the critcal section.
196897e9382dSDon Lewis 		 */
1969*8bb173fbSAlexander Motin 		TDQ_LOCK(tdq);
1970*8bb173fbSAlexander Motin 		if (tdq->tdq_load > 0)
197197e9382dSDon Lewis 			break;
1972*8bb173fbSAlexander Motin 		if (TDQ_TRYLOCK_FLAGS(steal, MTX_DUPOK) == 0)
1973*8bb173fbSAlexander Motin 			break;
197497e9382dSDon Lewis 		/*
197597e9382dSDon Lewis 		 * The data returned by sched_highest() is stale and
197697e9382dSDon Lewis                  * the chosen CPU no longer has an eligible thread.
197797e9382dSDon Lewis 		 */
197897e9382dSDon Lewis 		if (steal->tdq_load < steal_thresh ||
197997e9382dSDon Lewis 		    steal->tdq_transferable == 0) {
198097e9382dSDon Lewis 			TDQ_UNLOCK(steal);
198197e9382dSDon Lewis 			break;
198297e9382dSDon Lewis 		}
198397e9382dSDon Lewis 		/*
198497e9382dSDon Lewis 		 * If we fail to acquire one due to affinity restrictions,
198597e9382dSDon Lewis 		 * bail out and let the idle thread to a more complete search
198697e9382dSDon Lewis 		 * outside of a critical section.
198797e9382dSDon Lewis 		 */
198897e9382dSDon Lewis 		if (tdq_move(steal, tdq) == NULL) {
198997e9382dSDon Lewis 			TDQ_UNLOCK(steal);
199097e9382dSDon Lewis 			break;
199197e9382dSDon Lewis 		}
199297e9382dSDon Lewis 		TDQ_UNLOCK(steal);
199397e9382dSDon Lewis 		break;
199497e9382dSDon Lewis 	}
199597e9382dSDon Lewis 	spinlock_exit();
199697e9382dSDon Lewis }
19974c8a8cfcSKonstantin Belousov #endif
199897e9382dSDon Lewis 
199997e9382dSDon Lewis /*
2000c47f202bSJeff Roberson  * Handle migration from sched_switch().  This happens only for
2001c47f202bSJeff Roberson  * cpu binding.
2002c47f202bSJeff Roberson  */
2003c47f202bSJeff Roberson static struct mtx *
2004c47f202bSJeff Roberson sched_switch_migrate(struct tdq *tdq, struct thread *td, int flags)
2005c47f202bSJeff Roberson {
2006c47f202bSJeff Roberson 	struct tdq *tdn;
2007c47f202bSJeff Roberson 
2008686bcb5cSJeff Roberson 	KASSERT(THREAD_CAN_MIGRATE(td) ||
2009686bcb5cSJeff Roberson 	    (td_get_sched(td)->ts_flags & TSF_BOUND) != 0,
2010686bcb5cSJeff Roberson 	    ("Thread %p shouldn't migrate", td));
2011efe67753SNathan Whitehorn 	KASSERT(!CPU_ABSENT(td_get_sched(td)->ts_cpu), ("sched_switch_migrate: "
2012efe67753SNathan Whitehorn 	    "thread %s queued on absent CPU %d.", td->td_name,
2013efe67753SNathan Whitehorn 	    td_get_sched(td)->ts_cpu));
201493ccd6bfSKonstantin Belousov 	tdn = TDQ_CPU(td_get_sched(td)->ts_cpu);
2015c47f202bSJeff Roberson #ifdef SMP
20169727e637SJeff Roberson 	tdq_load_rem(tdq, td);
2017c47f202bSJeff Roberson 	/*
2018686bcb5cSJeff Roberson 	 * Do the lock dance required to avoid LOR.  We have an
2019686bcb5cSJeff Roberson 	 * extra spinlock nesting from sched_switch() which will
2020686bcb5cSJeff Roberson 	 * prevent preemption while we're holding neither run-queue lock.
2021c47f202bSJeff Roberson 	 */
2022686bcb5cSJeff Roberson 	TDQ_UNLOCK(tdq);
2023686bcb5cSJeff Roberson 	TDQ_LOCK(tdn);
2024c47f202bSJeff Roberson 	tdq_add(tdn, td, flags);
202527ee18adSRyan Stone 	tdq_notify(tdn, td);
2026c47f202bSJeff Roberson 	TDQ_UNLOCK(tdn);
2027686bcb5cSJeff Roberson 	TDQ_LOCK(tdq);
2028c47f202bSJeff Roberson #endif
2029c47f202bSJeff Roberson 	return (TDQ_LOCKPTR(tdn));
2030c47f202bSJeff Roberson }
2031c47f202bSJeff Roberson 
2032c47f202bSJeff Roberson /*
203361a74c5cSJeff Roberson  * thread_lock_unblock() that does not assume td_lock is blocked.
2034ae7a6b38SJeff Roberson  */
2035ae7a6b38SJeff Roberson static inline void
2036ae7a6b38SJeff Roberson thread_unblock_switch(struct thread *td, struct mtx *mtx)
2037ae7a6b38SJeff Roberson {
2038ae7a6b38SJeff Roberson 	atomic_store_rel_ptr((volatile uintptr_t *)&td->td_lock,
2039ae7a6b38SJeff Roberson 	    (uintptr_t)mtx);
2040ae7a6b38SJeff Roberson }
2041ae7a6b38SJeff Roberson 
2042ae7a6b38SJeff Roberson /*
2043ae7a6b38SJeff Roberson  * Switch threads.  This function has to handle threads coming in while
2044ae7a6b38SJeff Roberson  * blocked for some reason, running, or idle.  It also must deal with
2045ae7a6b38SJeff Roberson  * migrating a thread from one queue to another as running threads may
2046ae7a6b38SJeff Roberson  * be assigned elsewhere via binding.
2047ae7a6b38SJeff Roberson  */
20483db720fdSDavid Xu void
2049686bcb5cSJeff Roberson sched_switch(struct thread *td, int flags)
205035e6168fSJeff Roberson {
2051686bcb5cSJeff Roberson 	struct thread *newtd;
2052c02bbb43SJeff Roberson 	struct tdq *tdq;
2053ad1e7d28SJulian Elischer 	struct td_sched *ts;
2054ae7a6b38SJeff Roberson 	struct mtx *mtx;
2055c47f202bSJeff Roberson 	int srqflag;
20563d7f4117SAlexander Motin 	int cpuid, preempted;
205735e6168fSJeff Roberson 
20587b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
205935e6168fSJeff Roberson 
2060ae7a6b38SJeff Roberson 	cpuid = PCPU_GET(cpuid);
2061018ff686SJeff Roberson 	tdq = TDQ_SELF();
206293ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
20637295465eSAlexander Motin 	sched_pctcpu_update(ts, 1);
2064ae7a6b38SJeff Roberson 	ts->ts_rltick = ticks;
2065060563ecSJulian Elischer 	td->td_lastcpu = td->td_oncpu;
2066ad9dadc4SAndriy Gapon 	preempted = (td->td_flags & TDF_SLICEEND) == 0 &&
2067ad9dadc4SAndriy Gapon 	    (flags & SW_PREEMPT) != 0;
20683d7f4117SAlexander Motin 	td->td_flags &= ~(TDF_NEEDRESCHED | TDF_SLICEEND);
206977918643SStephan Uphoff 	td->td_owepreempt = 0;
20707789ab32SMark Johnston 	tdq->tdq_owepreempt = 0;
20712c27cb3aSAlexander Motin 	if (!TD_IS_IDLETHREAD(td))
20721690c6c1SJeff Roberson 		tdq->tdq_switchcnt++;
20737789ab32SMark Johnston 
2074b11fdad0SJeff Roberson 	/*
2075686bcb5cSJeff Roberson 	 * Always block the thread lock so we can drop the tdq lock early.
2076b11fdad0SJeff Roberson 	 */
2077686bcb5cSJeff Roberson 	mtx = thread_lock_block(td);
2078686bcb5cSJeff Roberson 	spinlock_enter();
2079486a9414SJulian Elischer 	if (TD_IS_IDLETHREAD(td)) {
2080686bcb5cSJeff Roberson 		MPASS(mtx == TDQ_LOCKPTR(tdq));
2081bf0acc27SJohn Baldwin 		TD_SET_CAN_RUN(td);
20827b20fb19SJeff Roberson 	} else if (TD_IS_RUNNING(td)) {
2083686bcb5cSJeff Roberson 		MPASS(mtx == TDQ_LOCKPTR(tdq));
20843d7f4117SAlexander Motin 		srqflag = preempted ?
2085598b368dSJeff Roberson 		    SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
2086c47f202bSJeff Roberson 		    SRQ_OURSELF|SRQ_YIELDING;
2087ba4932b5SMatthew D Fleming #ifdef SMP
20880f7a0ebdSMatthew D Fleming 		if (THREAD_CAN_MIGRATE(td) && !THREAD_CAN_SCHED(td, ts->ts_cpu))
20890f7a0ebdSMatthew D Fleming 			ts->ts_cpu = sched_pickcpu(td, 0);
2090ba4932b5SMatthew D Fleming #endif
2091c47f202bSJeff Roberson 		if (ts->ts_cpu == cpuid)
20929727e637SJeff Roberson 			tdq_runq_add(tdq, td, srqflag);
2093686bcb5cSJeff Roberson 		else
2094c47f202bSJeff Roberson 			mtx = sched_switch_migrate(tdq, td, srqflag);
2095ae7a6b38SJeff Roberson 	} else {
2096ae7a6b38SJeff Roberson 		/* This thread must be going to sleep. */
209761a74c5cSJeff Roberson 		if (mtx != TDQ_LOCKPTR(tdq)) {
209861a74c5cSJeff Roberson 			mtx_unlock_spin(mtx);
209961a74c5cSJeff Roberson 			TDQ_LOCK(tdq);
210061a74c5cSJeff Roberson 		}
21019727e637SJeff Roberson 		tdq_load_rem(tdq, td);
21024c8a8cfcSKonstantin Belousov #ifdef SMP
210397e9382dSDon Lewis 		if (tdq->tdq_load == 0)
210497e9382dSDon Lewis 			tdq_trysteal(tdq);
21054c8a8cfcSKonstantin Belousov #endif
2106ae7a6b38SJeff Roberson 	}
2107afa0a46cSAndriy Gapon 
2108afa0a46cSAndriy Gapon #if (KTR_COMPILE & KTR_SCHED) != 0
2109afa0a46cSAndriy Gapon 	if (TD_IS_IDLETHREAD(td))
2110afa0a46cSAndriy Gapon 		KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "idle",
2111afa0a46cSAndriy Gapon 		    "prio:%d", td->td_priority);
2112afa0a46cSAndriy Gapon 	else
2113afa0a46cSAndriy Gapon 		KTR_STATE3(KTR_SCHED, "thread", sched_tdname(td), KTDSTATE(td),
2114afa0a46cSAndriy Gapon 		    "prio:%d", td->td_priority, "wmesg:\"%s\"", td->td_wmesg,
2115afa0a46cSAndriy Gapon 		    "lockname:\"%s\"", td->td_lockname);
2116afa0a46cSAndriy Gapon #endif
2117afa0a46cSAndriy Gapon 
2118ae7a6b38SJeff Roberson 	/*
2119ae7a6b38SJeff Roberson 	 * We enter here with the thread blocked and assigned to the
2120ae7a6b38SJeff Roberson 	 * appropriate cpu run-queue or sleep-queue and with the current
2121ae7a6b38SJeff Roberson 	 * thread-queue locked.
2122ae7a6b38SJeff Roberson 	 */
2123ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED | MA_NOTRECURSED);
21242454aaf5SJeff Roberson 	newtd = choosethread();
2125686bcb5cSJeff Roberson 	sched_pctcpu_update(td_get_sched(newtd), 0);
2126686bcb5cSJeff Roberson 	TDQ_UNLOCK(tdq);
2127686bcb5cSJeff Roberson 
2128ae7a6b38SJeff Roberson 	/*
2129ae7a6b38SJeff Roberson 	 * Call the MD code to switch contexts if necessary.
2130ae7a6b38SJeff Roberson 	 */
2131ebccf1e3SJoseph Koshy 	if (td != newtd) {
2132ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
2133ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
2134ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_OUT);
2135ebccf1e3SJoseph Koshy #endif
2136d9fae5abSAndriy Gapon 		SDT_PROBE2(sched, , , off__cpu, newtd, newtd->td_proc);
21376f5f25e5SJohn Birrell 
21386f5f25e5SJohn Birrell #ifdef KDTRACE_HOOKS
21396f5f25e5SJohn Birrell 		/*
21406f5f25e5SJohn Birrell 		 * If DTrace has set the active vtime enum to anything
21416f5f25e5SJohn Birrell 		 * other than INACTIVE (0), then it should have set the
21426f5f25e5SJohn Birrell 		 * function to call.
21436f5f25e5SJohn Birrell 		 */
21446f5f25e5SJohn Birrell 		if (dtrace_vtime_active)
21456f5f25e5SJohn Birrell 			(*dtrace_vtime_switch_func)(newtd);
21466f5f25e5SJohn Birrell #endif
2147686bcb5cSJeff Roberson 		td->td_oncpu = NOCPU;
2148ae7a6b38SJeff Roberson 		cpu_switch(td, newtd, mtx);
2149a89c2c8cSMark Johnston 		cpuid = td->td_oncpu = PCPU_GET(cpuid);
2150b3e9e682SRyan Stone 
2151d9fae5abSAndriy Gapon 		SDT_PROBE0(sched, , , on__cpu);
2152ebccf1e3SJoseph Koshy #ifdef	HWPMC_HOOKS
2153ebccf1e3SJoseph Koshy 		if (PMC_PROC_IS_USING_PMCS(td->td_proc))
2154ebccf1e3SJoseph Koshy 			PMC_SWITCH_CONTEXT(td, PMC_FN_CSW_IN);
2155ebccf1e3SJoseph Koshy #endif
2156b3e9e682SRyan Stone 	} else {
2157ae7a6b38SJeff Roberson 		thread_unblock_switch(td, mtx);
2158d9fae5abSAndriy Gapon 		SDT_PROBE0(sched, , , remain__cpu);
2159b3e9e682SRyan Stone 	}
2160686bcb5cSJeff Roberson 	KASSERT(curthread->td_md.md_spinlock_count == 1,
2161686bcb5cSJeff Roberson 	    ("invalid count %d", curthread->td_md.md_spinlock_count));
2162afa0a46cSAndriy Gapon 
2163afa0a46cSAndriy Gapon 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "running",
2164afa0a46cSAndriy Gapon 	    "prio:%d", td->td_priority);
216535e6168fSJeff Roberson }
216635e6168fSJeff Roberson 
2167ae7a6b38SJeff Roberson /*
2168ae7a6b38SJeff Roberson  * Adjust thread priorities as a result of a nice request.
2169ae7a6b38SJeff Roberson  */
217035e6168fSJeff Roberson void
2171fa885116SJulian Elischer sched_nice(struct proc *p, int nice)
217235e6168fSJeff Roberson {
217335e6168fSJeff Roberson 	struct thread *td;
217435e6168fSJeff Roberson 
2175fa885116SJulian Elischer 	PROC_LOCK_ASSERT(p, MA_OWNED);
2176e7d50326SJeff Roberson 
2177fa885116SJulian Elischer 	p->p_nice = nice;
21788460a577SJohn Birrell 	FOREACH_THREAD_IN_PROC(p, td) {
21797b20fb19SJeff Roberson 		thread_lock(td);
21808460a577SJohn Birrell 		sched_priority(td);
2181e7d50326SJeff Roberson 		sched_prio(td, td->td_base_user_pri);
21827b20fb19SJeff Roberson 		thread_unlock(td);
218335e6168fSJeff Roberson 	}
2184fa885116SJulian Elischer }
218535e6168fSJeff Roberson 
2186ae7a6b38SJeff Roberson /*
2187ae7a6b38SJeff Roberson  * Record the sleep time for the interactivity scorer.
2188ae7a6b38SJeff Roberson  */
218935e6168fSJeff Roberson void
2190c5aa6b58SJeff Roberson sched_sleep(struct thread *td, int prio)
219135e6168fSJeff Roberson {
2192e7d50326SJeff Roberson 
21937b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
219435e6168fSJeff Roberson 
219554b0e65fSJeff Roberson 	td->td_slptick = ticks;
219617c4c356SKonstantin Belousov 	if (TD_IS_SUSPENDED(td) || prio >= PSOCK)
2197c5aa6b58SJeff Roberson 		td->td_flags |= TDF_CANSWAP;
21982dc29adbSJohn Baldwin 	if (PRI_BASE(td->td_pri_class) != PRI_TIMESHARE)
21992dc29adbSJohn Baldwin 		return;
22000502fe2eSJeff Roberson 	if (static_boost == 1 && prio)
2201c5aa6b58SJeff Roberson 		sched_prio(td, prio);
22020502fe2eSJeff Roberson 	else if (static_boost && td->td_priority > static_boost)
22030502fe2eSJeff Roberson 		sched_prio(td, static_boost);
220435e6168fSJeff Roberson }
220535e6168fSJeff Roberson 
2206ae7a6b38SJeff Roberson /*
2207ae7a6b38SJeff Roberson  * Schedule a thread to resume execution and record how long it voluntarily
2208ae7a6b38SJeff Roberson  * slept.  We also update the pctcpu, interactivity, and priority.
220961a74c5cSJeff Roberson  *
221061a74c5cSJeff Roberson  * Requires the thread lock on entry, drops on exit.
2211ae7a6b38SJeff Roberson  */
221235e6168fSJeff Roberson void
221361a74c5cSJeff Roberson sched_wakeup(struct thread *td, int srqflags)
221435e6168fSJeff Roberson {
221514618990SJeff Roberson 	struct td_sched *ts;
2216ae7a6b38SJeff Roberson 	int slptick;
2217e7d50326SJeff Roberson 
22187b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
221993ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
2220c5aa6b58SJeff Roberson 	td->td_flags &= ~TDF_CANSWAP;
222161a74c5cSJeff Roberson 
222235e6168fSJeff Roberson 	/*
2223e7d50326SJeff Roberson 	 * If we slept for more than a tick update our interactivity and
2224e7d50326SJeff Roberson 	 * priority.
222535e6168fSJeff Roberson 	 */
222654b0e65fSJeff Roberson 	slptick = td->td_slptick;
222754b0e65fSJeff Roberson 	td->td_slptick = 0;
2228ae7a6b38SJeff Roberson 	if (slptick && slptick != ticks) {
22297295465eSAlexander Motin 		ts->ts_slptime += (ticks - slptick) << SCHED_TICK_SHIFT;
22308460a577SJohn Birrell 		sched_interact_update(td);
22317295465eSAlexander Motin 		sched_pctcpu_update(ts, 0);
2232f1e8dc4aSJeff Roberson 	}
22335e5c3873SJeff Roberson 	/*
22345e5c3873SJeff Roberson 	 * Reset the slice value since we slept and advanced the round-robin.
22355e5c3873SJeff Roberson 	 */
22365e5c3873SJeff Roberson 	ts->ts_slice = 0;
223761a74c5cSJeff Roberson 	sched_add(td, SRQ_BORING | srqflags);
223835e6168fSJeff Roberson }
223935e6168fSJeff Roberson 
224035e6168fSJeff Roberson /*
224135e6168fSJeff Roberson  * Penalize the parent for creating a new child and initialize the child's
224235e6168fSJeff Roberson  * priority.
224335e6168fSJeff Roberson  */
224435e6168fSJeff Roberson void
22458460a577SJohn Birrell sched_fork(struct thread *td, struct thread *child)
224615dc847eSJeff Roberson {
22477b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
224893ccd6bfSKonstantin Belousov 	sched_pctcpu_update(td_get_sched(td), 1);
2249ad1e7d28SJulian Elischer 	sched_fork_thread(td, child);
2250e7d50326SJeff Roberson 	/*
2251e7d50326SJeff Roberson 	 * Penalize the parent and child for forking.
2252e7d50326SJeff Roberson 	 */
2253e7d50326SJeff Roberson 	sched_interact_fork(child);
2254e7d50326SJeff Roberson 	sched_priority(child);
225593ccd6bfSKonstantin Belousov 	td_get_sched(td)->ts_runtime += tickincr;
2256e7d50326SJeff Roberson 	sched_interact_update(td);
2257e7d50326SJeff Roberson 	sched_priority(td);
2258ad1e7d28SJulian Elischer }
2259ad1e7d28SJulian Elischer 
2260ae7a6b38SJeff Roberson /*
2261ae7a6b38SJeff Roberson  * Fork a new thread, may be within the same process.
2262ae7a6b38SJeff Roberson  */
2263ad1e7d28SJulian Elischer void
2264ad1e7d28SJulian Elischer sched_fork_thread(struct thread *td, struct thread *child)
2265ad1e7d28SJulian Elischer {
2266ad1e7d28SJulian Elischer 	struct td_sched *ts;
2267ad1e7d28SJulian Elischer 	struct td_sched *ts2;
22685e5c3873SJeff Roberson 	struct tdq *tdq;
22698460a577SJohn Birrell 
22705e5c3873SJeff Roberson 	tdq = TDQ_SELF();
22718b16c208SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2272e7d50326SJeff Roberson 	/*
2273e7d50326SJeff Roberson 	 * Initialize child.
2274e7d50326SJeff Roberson 	 */
227593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
227693ccd6bfSKonstantin Belousov 	ts2 = td_get_sched(child);
227792de34dfSJohn Baldwin 	child->td_oncpu = NOCPU;
227892de34dfSJohn Baldwin 	child->td_lastcpu = NOCPU;
22795e5c3873SJeff Roberson 	child->td_lock = TDQ_LOCKPTR(tdq);
22808b16c208SJeff Roberson 	child->td_cpuset = cpuset_ref(td->td_cpuset);
22813f289c3fSJeff Roberson 	child->td_domain.dr_policy = td->td_cpuset->cs_domain;
2282ad1e7d28SJulian Elischer 	ts2->ts_cpu = ts->ts_cpu;
22838b16c208SJeff Roberson 	ts2->ts_flags = 0;
2284e7d50326SJeff Roberson 	/*
228522d19207SJohn Baldwin 	 * Grab our parents cpu estimation information.
2286e7d50326SJeff Roberson 	 */
2287ad1e7d28SJulian Elischer 	ts2->ts_ticks = ts->ts_ticks;
2288ad1e7d28SJulian Elischer 	ts2->ts_ltick = ts->ts_ltick;
2289ad1e7d28SJulian Elischer 	ts2->ts_ftick = ts->ts_ftick;
229022d19207SJohn Baldwin 	/*
229122d19207SJohn Baldwin 	 * Do not inherit any borrowed priority from the parent.
229222d19207SJohn Baldwin 	 */
229322d19207SJohn Baldwin 	child->td_priority = child->td_base_pri;
2294e7d50326SJeff Roberson 	/*
2295e7d50326SJeff Roberson 	 * And update interactivity score.
2296e7d50326SJeff Roberson 	 */
2297ae7a6b38SJeff Roberson 	ts2->ts_slptime = ts->ts_slptime;
2298ae7a6b38SJeff Roberson 	ts2->ts_runtime = ts->ts_runtime;
22995e5c3873SJeff Roberson 	/* Attempt to quickly learn interactivity. */
23005e5c3873SJeff Roberson 	ts2->ts_slice = tdq_slice(tdq) - sched_slice_min;
23018f51ad55SJeff Roberson #ifdef KTR
23028f51ad55SJeff Roberson 	bzero(ts2->ts_name, sizeof(ts2->ts_name));
23038f51ad55SJeff Roberson #endif
230415dc847eSJeff Roberson }
230515dc847eSJeff Roberson 
2306ae7a6b38SJeff Roberson /*
2307ae7a6b38SJeff Roberson  * Adjust the priority class of a thread.
2308ae7a6b38SJeff Roberson  */
230915dc847eSJeff Roberson void
23108460a577SJohn Birrell sched_class(struct thread *td, int class)
231115dc847eSJeff Roberson {
231215dc847eSJeff Roberson 
23137b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
23148460a577SJohn Birrell 	if (td->td_pri_class == class)
231515dc847eSJeff Roberson 		return;
23168460a577SJohn Birrell 	td->td_pri_class = class;
231735e6168fSJeff Roberson }
231835e6168fSJeff Roberson 
231935e6168fSJeff Roberson /*
232035e6168fSJeff Roberson  * Return some of the child's priority and interactivity to the parent.
232135e6168fSJeff Roberson  */
232235e6168fSJeff Roberson void
2323fc6c30f6SJulian Elischer sched_exit(struct proc *p, struct thread *child)
232435e6168fSJeff Roberson {
2325e7d50326SJeff Roberson 	struct thread *td;
2326141ad61cSJeff Roberson 
23278f51ad55SJeff Roberson 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(child), "proc exit",
2328cd39bb09SXin LI 	    "prio:%d", child->td_priority);
2329374ae2a3SJeff Roberson 	PROC_LOCK_ASSERT(p, MA_OWNED);
2330e7d50326SJeff Roberson 	td = FIRST_THREAD_IN_PROC(p);
2331e7d50326SJeff Roberson 	sched_exit_thread(td, child);
2332ad1e7d28SJulian Elischer }
2333ad1e7d28SJulian Elischer 
2334ae7a6b38SJeff Roberson /*
2335ae7a6b38SJeff Roberson  * Penalize another thread for the time spent on this one.  This helps to
2336ae7a6b38SJeff Roberson  * worsen the priority and interactivity of processes which schedule batch
2337ae7a6b38SJeff Roberson  * jobs such as make.  This has little effect on the make process itself but
2338ae7a6b38SJeff Roberson  * causes new processes spawned by it to receive worse scores immediately.
2339ae7a6b38SJeff Roberson  */
2340ad1e7d28SJulian Elischer void
2341fc6c30f6SJulian Elischer sched_exit_thread(struct thread *td, struct thread *child)
2342ad1e7d28SJulian Elischer {
2343fc6c30f6SJulian Elischer 
23448f51ad55SJeff Roberson 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(child), "thread exit",
2345cd39bb09SXin LI 	    "prio:%d", child->td_priority);
2346e7d50326SJeff Roberson 	/*
2347e7d50326SJeff Roberson 	 * Give the child's runtime to the parent without returning the
2348e7d50326SJeff Roberson 	 * sleep time as a penalty to the parent.  This causes shells that
2349e7d50326SJeff Roberson 	 * launch expensive things to mark their children as expensive.
2350e7d50326SJeff Roberson 	 */
23517b20fb19SJeff Roberson 	thread_lock(td);
235293ccd6bfSKonstantin Belousov 	td_get_sched(td)->ts_runtime += td_get_sched(child)->ts_runtime;
2353fc6c30f6SJulian Elischer 	sched_interact_update(td);
2354e7d50326SJeff Roberson 	sched_priority(td);
23557b20fb19SJeff Roberson 	thread_unlock(td);
2356ad1e7d28SJulian Elischer }
2357ad1e7d28SJulian Elischer 
2358ff256d9cSJeff Roberson void
2359ff256d9cSJeff Roberson sched_preempt(struct thread *td)
2360ff256d9cSJeff Roberson {
2361ff256d9cSJeff Roberson 	struct tdq *tdq;
2362686bcb5cSJeff Roberson 	int flags;
2363ff256d9cSJeff Roberson 
2364b3e9e682SRyan Stone 	SDT_PROBE2(sched, , , surrender, td, td->td_proc);
2365b3e9e682SRyan Stone 
2366ff256d9cSJeff Roberson 	thread_lock(td);
2367ff256d9cSJeff Roberson 	tdq = TDQ_SELF();
2368ff256d9cSJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2369ff256d9cSJeff Roberson 	if (td->td_priority > tdq->tdq_lowpri) {
2370686bcb5cSJeff Roberson 		if (td->td_critnest == 1) {
23718df78c41SJeff Roberson 			flags = SW_INVOL | SW_PREEMPT;
2372686bcb5cSJeff Roberson 			flags |= TD_IS_IDLETHREAD(td) ? SWT_REMOTEWAKEIDLE :
2373686bcb5cSJeff Roberson 			    SWT_REMOTEPREEMPT;
2374686bcb5cSJeff Roberson 			mi_switch(flags);
2375686bcb5cSJeff Roberson 			/* Switch dropped thread lock. */
2376686bcb5cSJeff Roberson 			return;
2377686bcb5cSJeff Roberson 		}
2378ff256d9cSJeff Roberson 		td->td_owepreempt = 1;
23797789ab32SMark Johnston 	} else {
23807789ab32SMark Johnston 		tdq->tdq_owepreempt = 0;
2381ff256d9cSJeff Roberson 	}
2382ff256d9cSJeff Roberson 	thread_unlock(td);
2383ff256d9cSJeff Roberson }
2384ff256d9cSJeff Roberson 
2385ae7a6b38SJeff Roberson /*
2386ae7a6b38SJeff Roberson  * Fix priorities on return to user-space.  Priorities may be elevated due
2387ae7a6b38SJeff Roberson  * to static priorities in msleep() or similar.
2388ae7a6b38SJeff Roberson  */
2389ad1e7d28SJulian Elischer void
239028240885SMateusz Guzik sched_userret_slowpath(struct thread *td)
2391ad1e7d28SJulian Elischer {
239228240885SMateusz Guzik 
23937b20fb19SJeff Roberson 	thread_lock(td);
2394ad1e7d28SJulian Elischer 	td->td_priority = td->td_user_pri;
2395ad1e7d28SJulian Elischer 	td->td_base_pri = td->td_user_pri;
239662fa74d9SJeff Roberson 	tdq_setlowpri(TDQ_SELF(), td);
23977b20fb19SJeff Roberson 	thread_unlock(td);
2398ad1e7d28SJulian Elischer }
239935e6168fSJeff Roberson 
2400ae7a6b38SJeff Roberson /*
2401ae7a6b38SJeff Roberson  * Handle a stathz tick.  This is really only relevant for timeshare
2402ae7a6b38SJeff Roberson  * threads.
2403ae7a6b38SJeff Roberson  */
240435e6168fSJeff Roberson void
2405c3cccf95SJeff Roberson sched_clock(struct thread *td, int cnt)
240635e6168fSJeff Roberson {
2407ad1e7d28SJulian Elischer 	struct tdq *tdq;
2408ad1e7d28SJulian Elischer 	struct td_sched *ts;
240935e6168fSJeff Roberson 
2410ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
24113f872f85SJeff Roberson 	tdq = TDQ_SELF();
24127fcf154aSJeff Roberson #ifdef SMP
24137fcf154aSJeff Roberson 	/*
24147fcf154aSJeff Roberson 	 * We run the long term load balancer infrequently on the first cpu.
24157fcf154aSJeff Roberson 	 */
2416c3cccf95SJeff Roberson 	if (balance_tdq == tdq && smp_started != 0 && rebalance != 0 &&
2417c3cccf95SJeff Roberson 	    balance_ticks != 0) {
2418c3cccf95SJeff Roberson 		balance_ticks -= cnt;
2419c3cccf95SJeff Roberson 		if (balance_ticks <= 0)
24207fcf154aSJeff Roberson 			sched_balance();
24217fcf154aSJeff Roberson 	}
24227fcf154aSJeff Roberson #endif
24233f872f85SJeff Roberson 	/*
24241690c6c1SJeff Roberson 	 * Save the old switch count so we have a record of the last ticks
24251690c6c1SJeff Roberson 	 * activity.   Initialize the new switch count based on our load.
24261690c6c1SJeff Roberson 	 * If there is some activity seed it to reflect that.
24271690c6c1SJeff Roberson 	 */
24281690c6c1SJeff Roberson 	tdq->tdq_oldswitchcnt = tdq->tdq_switchcnt;
24296c47aaaeSJeff Roberson 	tdq->tdq_switchcnt = tdq->tdq_load;
24301690c6c1SJeff Roberson 	/*
24313f872f85SJeff Roberson 	 * Advance the insert index once for each tick to ensure that all
24323f872f85SJeff Roberson 	 * threads get a chance to run.
24333f872f85SJeff Roberson 	 */
24343f872f85SJeff Roberson 	if (tdq->tdq_idx == tdq->tdq_ridx) {
24353f872f85SJeff Roberson 		tdq->tdq_idx = (tdq->tdq_idx + 1) % RQ_NQS;
24363f872f85SJeff Roberson 		if (TAILQ_EMPTY(&tdq->tdq_timeshare.rq_queues[tdq->tdq_ridx]))
24373f872f85SJeff Roberson 			tdq->tdq_ridx = tdq->tdq_idx;
24383f872f85SJeff Roberson 	}
243993ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
24407295465eSAlexander Motin 	sched_pctcpu_update(ts, 1);
2441c3cccf95SJeff Roberson 	if ((td->td_pri_class & PRI_FIFO_BIT) || TD_IS_IDLETHREAD(td))
2442a8949de2SJeff Roberson 		return;
2443c3cccf95SJeff Roberson 
2444c9a8cba4SJohn Baldwin 	if (PRI_BASE(td->td_pri_class) == PRI_TIMESHARE) {
2445a8949de2SJeff Roberson 		/*
2446fd0b8c78SJeff Roberson 		 * We used a tick; charge it to the thread so
2447fd0b8c78SJeff Roberson 		 * that we can compute our interactivity.
244815dc847eSJeff Roberson 		 */
2449c3cccf95SJeff Roberson 		td_get_sched(td)->ts_runtime += tickincr * cnt;
24508460a577SJohn Birrell 		sched_interact_update(td);
245173daf66fSJeff Roberson 		sched_priority(td);
2452fd0b8c78SJeff Roberson 	}
2453579895dfSAlexander Motin 
245435e6168fSJeff Roberson 	/*
2455579895dfSAlexander Motin 	 * Force a context switch if the current thread has used up a full
2456579895dfSAlexander Motin 	 * time slice (default is 100ms).
245735e6168fSJeff Roberson 	 */
2458c3cccf95SJeff Roberson 	ts->ts_slice += cnt;
2459c3cccf95SJeff Roberson 	if (ts->ts_slice >= tdq_slice(tdq)) {
24605e5c3873SJeff Roberson 		ts->ts_slice = 0;
24613d7f4117SAlexander Motin 		td->td_flags |= TDF_NEEDRESCHED | TDF_SLICEEND;
246235e6168fSJeff Roberson 	}
2463579895dfSAlexander Motin }
246435e6168fSJeff Roberson 
2465ccd0ec40SKonstantin Belousov u_int
2466ccd0ec40SKonstantin Belousov sched_estcpu(struct thread *td __unused)
2467ae7a6b38SJeff Roberson {
2468ae7a6b38SJeff Roberson 
2469ccd0ec40SKonstantin Belousov 	return (0);
2470ae7a6b38SJeff Roberson }
2471ae7a6b38SJeff Roberson 
2472ae7a6b38SJeff Roberson /*
2473ae7a6b38SJeff Roberson  * Return whether the current CPU has runnable tasks.  Used for in-kernel
2474ae7a6b38SJeff Roberson  * cooperative idle threads.
2475ae7a6b38SJeff Roberson  */
247635e6168fSJeff Roberson int
247735e6168fSJeff Roberson sched_runnable(void)
247835e6168fSJeff Roberson {
2479ad1e7d28SJulian Elischer 	struct tdq *tdq;
2480b90816f1SJeff Roberson 	int load;
248135e6168fSJeff Roberson 
2482b90816f1SJeff Roberson 	load = 1;
2483b90816f1SJeff Roberson 
2484ad1e7d28SJulian Elischer 	tdq = TDQ_SELF();
24853f741ca1SJeff Roberson 	if ((curthread->td_flags & TDF_IDLETD) != 0) {
2486d2ad694cSJeff Roberson 		if (tdq->tdq_load > 0)
24873f741ca1SJeff Roberson 			goto out;
24883f741ca1SJeff Roberson 	} else
2489d2ad694cSJeff Roberson 		if (tdq->tdq_load - 1 > 0)
2490b90816f1SJeff Roberson 			goto out;
2491b90816f1SJeff Roberson 	load = 0;
2492b90816f1SJeff Roberson out:
2493b90816f1SJeff Roberson 	return (load);
249435e6168fSJeff Roberson }
249535e6168fSJeff Roberson 
2496ae7a6b38SJeff Roberson /*
2497ae7a6b38SJeff Roberson  * Choose the highest priority thread to run.  The thread is removed from
2498ae7a6b38SJeff Roberson  * the run-queue while running however the load remains.  For SMP we set
2499ae7a6b38SJeff Roberson  * the tdq in the global idle bitmask if it idles here.
2500ae7a6b38SJeff Roberson  */
25017a5e5e2aSJeff Roberson struct thread *
2502c9f25d8fSJeff Roberson sched_choose(void)
2503c9f25d8fSJeff Roberson {
25049727e637SJeff Roberson 	struct thread *td;
2505ae7a6b38SJeff Roberson 	struct tdq *tdq;
2506ae7a6b38SJeff Roberson 
2507ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2508ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
25099727e637SJeff Roberson 	td = tdq_choose(tdq);
25109727e637SJeff Roberson 	if (td) {
25119727e637SJeff Roberson 		tdq_runq_rem(tdq, td);
25120502fe2eSJeff Roberson 		tdq->tdq_lowpri = td->td_priority;
25139727e637SJeff Roberson 		return (td);
251435e6168fSJeff Roberson 	}
25150502fe2eSJeff Roberson 	tdq->tdq_lowpri = PRI_MAX_IDLE;
251662fa74d9SJeff Roberson 	return (PCPU_GET(idlethread));
25177a5e5e2aSJeff Roberson }
25187a5e5e2aSJeff Roberson 
2519ae7a6b38SJeff Roberson /*
2520ae7a6b38SJeff Roberson  * Set owepreempt if necessary.  Preemption never happens directly in ULE,
2521ae7a6b38SJeff Roberson  * we always request it once we exit a critical section.
2522ae7a6b38SJeff Roberson  */
2523ae7a6b38SJeff Roberson static inline void
2524ae7a6b38SJeff Roberson sched_setpreempt(struct thread *td)
25257a5e5e2aSJeff Roberson {
25267a5e5e2aSJeff Roberson 	struct thread *ctd;
25277a5e5e2aSJeff Roberson 	int cpri;
25287a5e5e2aSJeff Roberson 	int pri;
25297a5e5e2aSJeff Roberson 
2530ff256d9cSJeff Roberson 	THREAD_LOCK_ASSERT(curthread, MA_OWNED);
2531ff256d9cSJeff Roberson 
25327a5e5e2aSJeff Roberson 	ctd = curthread;
25337a5e5e2aSJeff Roberson 	pri = td->td_priority;
25347a5e5e2aSJeff Roberson 	cpri = ctd->td_priority;
2535ff256d9cSJeff Roberson 	if (pri < cpri)
2536ff256d9cSJeff Roberson 		ctd->td_flags |= TDF_NEEDRESCHED;
2537879e0604SMateusz Guzik 	if (KERNEL_PANICKED() || pri >= cpri || cold || TD_IS_INHIBITED(ctd))
2538ae7a6b38SJeff Roberson 		return;
2539ff256d9cSJeff Roberson 	if (!sched_shouldpreempt(pri, cpri, 0))
2540ae7a6b38SJeff Roberson 		return;
25417a5e5e2aSJeff Roberson 	ctd->td_owepreempt = 1;
254235e6168fSJeff Roberson }
254335e6168fSJeff Roberson 
2544ae7a6b38SJeff Roberson /*
254573daf66fSJeff Roberson  * Add a thread to a thread queue.  Select the appropriate runq and add the
254673daf66fSJeff Roberson  * thread to it.  This is the internal function called when the tdq is
254773daf66fSJeff Roberson  * predetermined.
2548ae7a6b38SJeff Roberson  */
254935e6168fSJeff Roberson void
2550ae7a6b38SJeff Roberson tdq_add(struct tdq *tdq, struct thread *td, int flags)
255135e6168fSJeff Roberson {
2552c9f25d8fSJeff Roberson 
2553ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
255461a74c5cSJeff Roberson 	THREAD_LOCK_BLOCKED_ASSERT(td, MA_OWNED);
25557a5e5e2aSJeff Roberson 	KASSERT((td->td_inhibitors == 0),
25567a5e5e2aSJeff Roberson 	    ("sched_add: trying to run inhibited thread"));
25577a5e5e2aSJeff Roberson 	KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
25587a5e5e2aSJeff Roberson 	    ("sched_add: bad thread state"));
2559b61ce5b0SJeff Roberson 	KASSERT(td->td_flags & TDF_INMEM,
2560b61ce5b0SJeff Roberson 	    ("sched_add: thread swapped out"));
2561ae7a6b38SJeff Roberson 
2562ae7a6b38SJeff Roberson 	if (td->td_priority < tdq->tdq_lowpri)
2563ae7a6b38SJeff Roberson 		tdq->tdq_lowpri = td->td_priority;
25649727e637SJeff Roberson 	tdq_runq_add(tdq, td, flags);
25659727e637SJeff Roberson 	tdq_load_add(tdq, td);
2566ae7a6b38SJeff Roberson }
2567ae7a6b38SJeff Roberson 
2568ae7a6b38SJeff Roberson /*
2569ae7a6b38SJeff Roberson  * Select the target thread queue and add a thread to it.  Request
2570ae7a6b38SJeff Roberson  * preemption or IPI a remote processor if required.
257161a74c5cSJeff Roberson  *
257261a74c5cSJeff Roberson  * Requires the thread lock on entry, drops on exit.
2573ae7a6b38SJeff Roberson  */
2574ae7a6b38SJeff Roberson void
2575ae7a6b38SJeff Roberson sched_add(struct thread *td, int flags)
2576ae7a6b38SJeff Roberson {
2577ae7a6b38SJeff Roberson 	struct tdq *tdq;
25787b8bfa0dSJeff Roberson #ifdef SMP
2579ae7a6b38SJeff Roberson 	int cpu;
2580ae7a6b38SJeff Roberson #endif
25818f51ad55SJeff Roberson 
25828f51ad55SJeff Roberson 	KTR_STATE2(KTR_SCHED, "thread", sched_tdname(td), "runq add",
25838f51ad55SJeff Roberson 	    "prio:%d", td->td_priority, KTR_ATTR_LINKED,
25848f51ad55SJeff Roberson 	    sched_tdname(curthread));
25858f51ad55SJeff Roberson 	KTR_POINT1(KTR_SCHED, "thread", sched_tdname(curthread), "wokeup",
25868f51ad55SJeff Roberson 	    KTR_ATTR_LINKED, sched_tdname(td));
2587b3e9e682SRyan Stone 	SDT_PROBE4(sched, , , enqueue, td, td->td_proc, NULL,
2588b3e9e682SRyan Stone 	    flags & SRQ_PREEMPTED);
2589ae7a6b38SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
2590ae7a6b38SJeff Roberson 	/*
2591ae7a6b38SJeff Roberson 	 * Recalculate the priority before we select the target cpu or
2592ae7a6b38SJeff Roberson 	 * run-queue.
2593ae7a6b38SJeff Roberson 	 */
2594ae7a6b38SJeff Roberson 	if (PRI_BASE(td->td_pri_class) == PRI_TIMESHARE)
2595ae7a6b38SJeff Roberson 		sched_priority(td);
2596ae7a6b38SJeff Roberson #ifdef SMP
2597ae7a6b38SJeff Roberson 	/*
2598ae7a6b38SJeff Roberson 	 * Pick the destination cpu and if it isn't ours transfer to the
2599ae7a6b38SJeff Roberson 	 * target cpu.
2600ae7a6b38SJeff Roberson 	 */
26019727e637SJeff Roberson 	cpu = sched_pickcpu(td, flags);
26029727e637SJeff Roberson 	tdq = sched_setcpu(td, cpu, flags);
2603ae7a6b38SJeff Roberson 	tdq_add(tdq, td, flags);
260461a74c5cSJeff Roberson 	if (cpu != PCPU_GET(cpuid))
260527ee18adSRyan Stone 		tdq_notify(tdq, td);
260661a74c5cSJeff Roberson 	else if (!(flags & SRQ_YIELDING))
260761a74c5cSJeff Roberson 		sched_setpreempt(td);
2608ae7a6b38SJeff Roberson #else
2609ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2610ae7a6b38SJeff Roberson 	/*
2611ae7a6b38SJeff Roberson 	 * Now that the thread is moving to the run-queue, set the lock
2612ae7a6b38SJeff Roberson 	 * to the scheduler's lock.
2613ae7a6b38SJeff Roberson 	 */
2614e4894505SMark Johnston 	if (td->td_lock != TDQ_LOCKPTR(tdq)) {
2615e4894505SMark Johnston 		TDQ_LOCK(tdq);
261661a74c5cSJeff Roberson 		if ((flags & SRQ_HOLD) != 0)
261761a74c5cSJeff Roberson 			td->td_lock = TDQ_LOCKPTR(tdq);
261861a74c5cSJeff Roberson 		else
2619ae7a6b38SJeff Roberson 			thread_lock_set(td, TDQ_LOCKPTR(tdq));
2620e4894505SMark Johnston 	}
2621ae7a6b38SJeff Roberson 	tdq_add(tdq, td, flags);
2622ae7a6b38SJeff Roberson 	if (!(flags & SRQ_YIELDING))
2623ae7a6b38SJeff Roberson 		sched_setpreempt(td);
262461a74c5cSJeff Roberson #endif
262561a74c5cSJeff Roberson 	if (!(flags & SRQ_HOLDTD))
262661a74c5cSJeff Roberson 		thread_unlock(td);
262735e6168fSJeff Roberson }
262835e6168fSJeff Roberson 
2629ae7a6b38SJeff Roberson /*
2630ae7a6b38SJeff Roberson  * Remove a thread from a run-queue without running it.  This is used
2631ae7a6b38SJeff Roberson  * when we're stealing a thread from a remote queue.  Otherwise all threads
2632ae7a6b38SJeff Roberson  * exit by calling sched_exit_thread() and sched_throw() themselves.
2633ae7a6b38SJeff Roberson  */
263435e6168fSJeff Roberson void
26357cf90fb3SJeff Roberson sched_rem(struct thread *td)
263635e6168fSJeff Roberson {
2637ad1e7d28SJulian Elischer 	struct tdq *tdq;
26387cf90fb3SJeff Roberson 
26398f51ad55SJeff Roberson 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "runq rem",
26408f51ad55SJeff Roberson 	    "prio:%d", td->td_priority);
2641b3e9e682SRyan Stone 	SDT_PROBE3(sched, , , dequeue, td, td->td_proc, NULL);
264293ccd6bfSKonstantin Belousov 	tdq = TDQ_CPU(td_get_sched(td)->ts_cpu);
2643ae7a6b38SJeff Roberson 	TDQ_LOCK_ASSERT(tdq, MA_OWNED);
2644ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
26457a5e5e2aSJeff Roberson 	KASSERT(TD_ON_RUNQ(td),
2646ad1e7d28SJulian Elischer 	    ("sched_rem: thread not on run queue"));
26479727e637SJeff Roberson 	tdq_runq_rem(tdq, td);
26489727e637SJeff Roberson 	tdq_load_rem(tdq, td);
26497a5e5e2aSJeff Roberson 	TD_SET_CAN_RUN(td);
265062fa74d9SJeff Roberson 	if (td->td_priority == tdq->tdq_lowpri)
265162fa74d9SJeff Roberson 		tdq_setlowpri(tdq, NULL);
265235e6168fSJeff Roberson }
265335e6168fSJeff Roberson 
2654ae7a6b38SJeff Roberson /*
2655ae7a6b38SJeff Roberson  * Fetch cpu utilization information.  Updates on demand.
2656ae7a6b38SJeff Roberson  */
265735e6168fSJeff Roberson fixpt_t
26587cf90fb3SJeff Roberson sched_pctcpu(struct thread *td)
265935e6168fSJeff Roberson {
266035e6168fSJeff Roberson 	fixpt_t pctcpu;
2661ad1e7d28SJulian Elischer 	struct td_sched *ts;
266235e6168fSJeff Roberson 
266335e6168fSJeff Roberson 	pctcpu = 0;
266493ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
266535e6168fSJeff Roberson 
26663da35a0aSJohn Baldwin 	THREAD_LOCK_ASSERT(td, MA_OWNED);
26677295465eSAlexander Motin 	sched_pctcpu_update(ts, TD_IS_RUNNING(td));
2668ad1e7d28SJulian Elischer 	if (ts->ts_ticks) {
266935e6168fSJeff Roberson 		int rtick;
267035e6168fSJeff Roberson 
267135e6168fSJeff Roberson 		/* How many rtick per second ? */
2672e7d50326SJeff Roberson 		rtick = min(SCHED_TICK_HZ(ts) / SCHED_TICK_SECS, hz);
2673e7d50326SJeff Roberson 		pctcpu = (FSCALE * ((FSCALE * rtick)/hz)) >> FSHIFT;
267435e6168fSJeff Roberson 	}
267535e6168fSJeff Roberson 
267635e6168fSJeff Roberson 	return (pctcpu);
267735e6168fSJeff Roberson }
267835e6168fSJeff Roberson 
267962fa74d9SJeff Roberson /*
268062fa74d9SJeff Roberson  * Enforce affinity settings for a thread.  Called after adjustments to
268162fa74d9SJeff Roberson  * cpumask.
268262fa74d9SJeff Roberson  */
2683885d51a3SJeff Roberson void
2684885d51a3SJeff Roberson sched_affinity(struct thread *td)
2685885d51a3SJeff Roberson {
268662fa74d9SJeff Roberson #ifdef SMP
268762fa74d9SJeff Roberson 	struct td_sched *ts;
268862fa74d9SJeff Roberson 
268962fa74d9SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
269093ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
269162fa74d9SJeff Roberson 	if (THREAD_CAN_SCHED(td, ts->ts_cpu))
269262fa74d9SJeff Roberson 		return;
269353a6c8b3SJeff Roberson 	if (TD_ON_RUNQ(td)) {
269453a6c8b3SJeff Roberson 		sched_rem(td);
2695d8d5f036SJeff Roberson 		sched_add(td, SRQ_BORING | SRQ_HOLDTD);
269653a6c8b3SJeff Roberson 		return;
269753a6c8b3SJeff Roberson 	}
269862fa74d9SJeff Roberson 	if (!TD_IS_RUNNING(td))
269962fa74d9SJeff Roberson 		return;
270062fa74d9SJeff Roberson 	/*
27010f7a0ebdSMatthew D Fleming 	 * Force a switch before returning to userspace.  If the
27020f7a0ebdSMatthew D Fleming 	 * target thread is not running locally send an ipi to force
27030f7a0ebdSMatthew D Fleming 	 * the issue.
270462fa74d9SJeff Roberson 	 */
2705a8103ae8SJohn Baldwin 	td->td_flags |= TDF_NEEDRESCHED;
27060f7a0ebdSMatthew D Fleming 	if (td != curthread)
27070f7a0ebdSMatthew D Fleming 		ipi_cpu(ts->ts_cpu, IPI_PREEMPT);
270862fa74d9SJeff Roberson #endif
2709885d51a3SJeff Roberson }
2710885d51a3SJeff Roberson 
2711ae7a6b38SJeff Roberson /*
2712ae7a6b38SJeff Roberson  * Bind a thread to a target cpu.
2713ae7a6b38SJeff Roberson  */
27149bacd788SJeff Roberson void
27159bacd788SJeff Roberson sched_bind(struct thread *td, int cpu)
27169bacd788SJeff Roberson {
2717ad1e7d28SJulian Elischer 	struct td_sched *ts;
27189bacd788SJeff Roberson 
2719c47f202bSJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED|MA_NOTRECURSED);
27201d7830edSJohn Baldwin 	KASSERT(td == curthread, ("sched_bind: can only bind curthread"));
272193ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
27226b2f763fSJeff Roberson 	if (ts->ts_flags & TSF_BOUND)
2723c95d2db2SJeff Roberson 		sched_unbind(td);
27240f7a0ebdSMatthew D Fleming 	KASSERT(THREAD_CAN_MIGRATE(td), ("%p must be migratable", td));
2725ad1e7d28SJulian Elischer 	ts->ts_flags |= TSF_BOUND;
27266b2f763fSJeff Roberson 	sched_pin();
272780f86c9fSJeff Roberson 	if (PCPU_GET(cpuid) == cpu)
27289bacd788SJeff Roberson 		return;
27296b2f763fSJeff Roberson 	ts->ts_cpu = cpu;
27309bacd788SJeff Roberson 	/* When we return from mi_switch we'll be on the correct cpu. */
2731686bcb5cSJeff Roberson 	mi_switch(SW_VOL);
2732686bcb5cSJeff Roberson 	thread_lock(td);
27339bacd788SJeff Roberson }
27349bacd788SJeff Roberson 
2735ae7a6b38SJeff Roberson /*
2736ae7a6b38SJeff Roberson  * Release a bound thread.
2737ae7a6b38SJeff Roberson  */
27389bacd788SJeff Roberson void
27399bacd788SJeff Roberson sched_unbind(struct thread *td)
27409bacd788SJeff Roberson {
2741e7d50326SJeff Roberson 	struct td_sched *ts;
2742e7d50326SJeff Roberson 
27437b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
27441d7830edSJohn Baldwin 	KASSERT(td == curthread, ("sched_unbind: can only bind curthread"));
274593ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
27466b2f763fSJeff Roberson 	if ((ts->ts_flags & TSF_BOUND) == 0)
27476b2f763fSJeff Roberson 		return;
2748e7d50326SJeff Roberson 	ts->ts_flags &= ~TSF_BOUND;
2749e7d50326SJeff Roberson 	sched_unpin();
27509bacd788SJeff Roberson }
27519bacd788SJeff Roberson 
275235e6168fSJeff Roberson int
2753ebccf1e3SJoseph Koshy sched_is_bound(struct thread *td)
2754ebccf1e3SJoseph Koshy {
27557b20fb19SJeff Roberson 	THREAD_LOCK_ASSERT(td, MA_OWNED);
275693ccd6bfSKonstantin Belousov 	return (td_get_sched(td)->ts_flags & TSF_BOUND);
2757ebccf1e3SJoseph Koshy }
2758ebccf1e3SJoseph Koshy 
2759ae7a6b38SJeff Roberson /*
2760ae7a6b38SJeff Roberson  * Basic yield call.
2761ae7a6b38SJeff Roberson  */
276236ec198bSDavid Xu void
276336ec198bSDavid Xu sched_relinquish(struct thread *td)
276436ec198bSDavid Xu {
27657b20fb19SJeff Roberson 	thread_lock(td);
2766686bcb5cSJeff Roberson 	mi_switch(SW_VOL | SWT_RELINQUISH);
276736ec198bSDavid Xu }
276836ec198bSDavid Xu 
2769ae7a6b38SJeff Roberson /*
2770ae7a6b38SJeff Roberson  * Return the total system load.
2771ae7a6b38SJeff Roberson  */
2772ebccf1e3SJoseph Koshy int
277333916c36SJeff Roberson sched_load(void)
277433916c36SJeff Roberson {
277533916c36SJeff Roberson #ifdef SMP
277633916c36SJeff Roberson 	int total;
277733916c36SJeff Roberson 	int i;
277833916c36SJeff Roberson 
277933916c36SJeff Roberson 	total = 0;
27803aa6d94eSJohn Baldwin 	CPU_FOREACH(i)
278162fa74d9SJeff Roberson 		total += TDQ_CPU(i)->tdq_sysload;
278233916c36SJeff Roberson 	return (total);
278333916c36SJeff Roberson #else
2784d2ad694cSJeff Roberson 	return (TDQ_SELF()->tdq_sysload);
278533916c36SJeff Roberson #endif
278633916c36SJeff Roberson }
278733916c36SJeff Roberson 
278833916c36SJeff Roberson int
278935e6168fSJeff Roberson sched_sizeof_proc(void)
279035e6168fSJeff Roberson {
279135e6168fSJeff Roberson 	return (sizeof(struct proc));
279235e6168fSJeff Roberson }
279335e6168fSJeff Roberson 
279435e6168fSJeff Roberson int
279535e6168fSJeff Roberson sched_sizeof_thread(void)
279635e6168fSJeff Roberson {
279735e6168fSJeff Roberson 	return (sizeof(struct thread) + sizeof(struct td_sched));
279835e6168fSJeff Roberson }
2799b41f1452SDavid Xu 
280009c8a4ccSJeff Roberson #ifdef SMP
280109c8a4ccSJeff Roberson #define	TDQ_IDLESPIN(tdq)						\
280209c8a4ccSJeff Roberson     ((tdq)->tdq_cg != NULL && ((tdq)->tdq_cg->cg_flags & CG_FLAG_THREAD) == 0)
280309c8a4ccSJeff Roberson #else
280409c8a4ccSJeff Roberson #define	TDQ_IDLESPIN(tdq)	1
280509c8a4ccSJeff Roberson #endif
280609c8a4ccSJeff Roberson 
28077a5e5e2aSJeff Roberson /*
28087a5e5e2aSJeff Roberson  * The actual idle process.
28097a5e5e2aSJeff Roberson  */
28107a5e5e2aSJeff Roberson void
28117a5e5e2aSJeff Roberson sched_idletd(void *dummy)
28127a5e5e2aSJeff Roberson {
28137a5e5e2aSJeff Roberson 	struct thread *td;
2814ae7a6b38SJeff Roberson 	struct tdq *tdq;
28152c27cb3aSAlexander Motin 	int oldswitchcnt, switchcnt;
28161690c6c1SJeff Roberson 	int i;
28177a5e5e2aSJeff Roberson 
28187b55ab05SJeff Roberson 	mtx_assert(&Giant, MA_NOTOWNED);
28197a5e5e2aSJeff Roberson 	td = curthread;
2820ae7a6b38SJeff Roberson 	tdq = TDQ_SELF();
2821ba96d2d8SJohn Baldwin 	THREAD_NO_SLEEPING();
28222c27cb3aSAlexander Motin 	oldswitchcnt = -1;
2823ae7a6b38SJeff Roberson 	for (;;) {
28242c27cb3aSAlexander Motin 		if (tdq->tdq_load) {
28252c27cb3aSAlexander Motin 			thread_lock(td);
2826686bcb5cSJeff Roberson 			mi_switch(SW_VOL | SWT_IDLE);
28272c27cb3aSAlexander Motin 		}
28282c27cb3aSAlexander Motin 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
2829ae7a6b38SJeff Roberson #ifdef SMP
283097e9382dSDon Lewis 		if (always_steal || switchcnt != oldswitchcnt) {
28312c27cb3aSAlexander Motin 			oldswitchcnt = switchcnt;
28321690c6c1SJeff Roberson 			if (tdq_idled(tdq) == 0)
28331690c6c1SJeff Roberson 				continue;
28342c27cb3aSAlexander Motin 		}
28351690c6c1SJeff Roberson 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
28362fd4047fSAlexander Motin #else
28372fd4047fSAlexander Motin 		oldswitchcnt = switchcnt;
28382fd4047fSAlexander Motin #endif
28391690c6c1SJeff Roberson 		/*
28401690c6c1SJeff Roberson 		 * If we're switching very frequently, spin while checking
28411690c6c1SJeff Roberson 		 * for load rather than entering a low power state that
28427b55ab05SJeff Roberson 		 * may require an IPI.  However, don't do any busy
28437b55ab05SJeff Roberson 		 * loops while on SMT machines as this simply steals
28447b55ab05SJeff Roberson 		 * cycles from cores doing useful work.
28451690c6c1SJeff Roberson 		 */
284609c8a4ccSJeff Roberson 		if (TDQ_IDLESPIN(tdq) && switchcnt > sched_idlespinthresh) {
28471690c6c1SJeff Roberson 			for (i = 0; i < sched_idlespins; i++) {
28481690c6c1SJeff Roberson 				if (tdq->tdq_load)
28491690c6c1SJeff Roberson 					break;
28501690c6c1SJeff Roberson 				cpu_spinwait();
28511690c6c1SJeff Roberson 			}
28521690c6c1SJeff Roberson 		}
28532c27cb3aSAlexander Motin 
28542c27cb3aSAlexander Motin 		/* If there was context switch during spin, restart it. */
28556c47aaaeSJeff Roberson 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
28562c27cb3aSAlexander Motin 		if (tdq->tdq_load != 0 || switchcnt != oldswitchcnt)
28572c27cb3aSAlexander Motin 			continue;
28582c27cb3aSAlexander Motin 
28592c27cb3aSAlexander Motin 		/* Run main MD idle handler. */
28609f9ad565SAlexander Motin 		tdq->tdq_cpu_idle = 1;
286179654969SAlexander Motin 		/*
286279654969SAlexander Motin 		 * Make sure that tdq_cpu_idle update is globally visible
286379654969SAlexander Motin 		 * before cpu_idle() read tdq_load.  The order is important
286479654969SAlexander Motin 		 * to avoid race with tdq_notify.
286579654969SAlexander Motin 		 */
2866e8677f38SKonstantin Belousov 		atomic_thread_fence_seq_cst();
286797e9382dSDon Lewis 		/*
286897e9382dSDon Lewis 		 * Checking for again after the fence picks up assigned
286997e9382dSDon Lewis 		 * threads often enough to make it worthwhile to do so in
287097e9382dSDon Lewis 		 * order to avoid calling cpu_idle().
287197e9382dSDon Lewis 		 */
287297e9382dSDon Lewis 		if (tdq->tdq_load != 0) {
287397e9382dSDon Lewis 			tdq->tdq_cpu_idle = 0;
287497e9382dSDon Lewis 			continue;
287597e9382dSDon Lewis 		}
28762c27cb3aSAlexander Motin 		cpu_idle(switchcnt * 4 > sched_idlespinthresh);
28779f9ad565SAlexander Motin 		tdq->tdq_cpu_idle = 0;
28782c27cb3aSAlexander Motin 
28792c27cb3aSAlexander Motin 		/*
28802c27cb3aSAlexander Motin 		 * Account thread-less hardware interrupts and
28812c27cb3aSAlexander Motin 		 * other wakeup reasons equal to context switches.
28822c27cb3aSAlexander Motin 		 */
28832c27cb3aSAlexander Motin 		switchcnt = tdq->tdq_switchcnt + tdq->tdq_oldswitchcnt;
28842c27cb3aSAlexander Motin 		if (switchcnt != oldswitchcnt)
28852c27cb3aSAlexander Motin 			continue;
28862c27cb3aSAlexander Motin 		tdq->tdq_switchcnt++;
28872c27cb3aSAlexander Motin 		oldswitchcnt++;
2888ae7a6b38SJeff Roberson 	}
2889b41f1452SDavid Xu }
2890e7d50326SJeff Roberson 
28917b20fb19SJeff Roberson /*
28927b20fb19SJeff Roberson  * A CPU is entering for the first time or a thread is exiting.
28937b20fb19SJeff Roberson  */
28947b20fb19SJeff Roberson void
28957b20fb19SJeff Roberson sched_throw(struct thread *td)
28967b20fb19SJeff Roberson {
289759c68134SJeff Roberson 	struct thread *newtd;
2898ae7a6b38SJeff Roberson 	struct tdq *tdq;
2899ae7a6b38SJeff Roberson 
29001eb13fceSJeff Roberson 	if (__predict_false(td == NULL)) {
2901018ff686SJeff Roberson #ifdef SMP
2902018ff686SJeff Roberson 		PCPU_SET(sched, DPCPU_PTR(tdq));
2903018ff686SJeff Roberson #endif
2904ae7a6b38SJeff Roberson 		/* Correct spinlock nesting and acquire the correct lock. */
2905018ff686SJeff Roberson 		tdq = TDQ_SELF();
2906ae7a6b38SJeff Roberson 		TDQ_LOCK(tdq);
29077b20fb19SJeff Roberson 		spinlock_exit();
29087e3a96eaSJohn Baldwin 		PCPU_SET(switchtime, cpu_ticks());
29097e3a96eaSJohn Baldwin 		PCPU_SET(switchticks, ticks);
2910e1504695SJeff Roberson 		PCPU_GET(idlethread)->td_lock = TDQ_LOCKPTR(tdq);
29117b20fb19SJeff Roberson 	} else {
2912018ff686SJeff Roberson 		tdq = TDQ_SELF();
2913686bcb5cSJeff Roberson 		THREAD_LOCK_ASSERT(td, MA_OWNED);
2914686bcb5cSJeff Roberson 		THREAD_LOCKPTR_ASSERT(td, TDQ_LOCKPTR(tdq));
29159727e637SJeff Roberson 		tdq_load_rem(tdq, td);
291692de34dfSJohn Baldwin 		td->td_lastcpu = td->td_oncpu;
291792de34dfSJohn Baldwin 		td->td_oncpu = NOCPU;
29181eb13fceSJeff Roberson 		thread_lock_block(td);
29197b20fb19SJeff Roberson 	}
292059c68134SJeff Roberson 	newtd = choosethread();
2921686bcb5cSJeff Roberson 	spinlock_enter();
2922686bcb5cSJeff Roberson 	TDQ_UNLOCK(tdq);
2923686bcb5cSJeff Roberson 	KASSERT(curthread->td_md.md_spinlock_count == 1,
2924686bcb5cSJeff Roberson 	    ("invalid count %d", curthread->td_md.md_spinlock_count));
29251eb13fceSJeff Roberson 	/* doesn't return */
29261eb13fceSJeff Roberson 	if (__predict_false(td == NULL))
292759c68134SJeff Roberson 		cpu_throw(td, newtd);		/* doesn't return */
29281eb13fceSJeff Roberson 	else
29291eb13fceSJeff Roberson 		cpu_switch(td, newtd, TDQ_LOCKPTR(tdq));
29307b20fb19SJeff Roberson }
29317b20fb19SJeff Roberson 
2932ae7a6b38SJeff Roberson /*
2933ae7a6b38SJeff Roberson  * This is called from fork_exit().  Just acquire the correct locks and
2934ae7a6b38SJeff Roberson  * let fork do the rest of the work.
2935ae7a6b38SJeff Roberson  */
29367b20fb19SJeff Roberson void
2937fe54587fSJeff Roberson sched_fork_exit(struct thread *td)
29387b20fb19SJeff Roberson {
2939ae7a6b38SJeff Roberson 	struct tdq *tdq;
2940ae7a6b38SJeff Roberson 	int cpuid;
29417b20fb19SJeff Roberson 
29427b20fb19SJeff Roberson 	/*
29437b20fb19SJeff Roberson 	 * Finish setting up thread glue so that it begins execution in a
2944ae7a6b38SJeff Roberson 	 * non-nested critical section with the scheduler lock held.
29457b20fb19SJeff Roberson 	 */
2946686bcb5cSJeff Roberson 	KASSERT(curthread->td_md.md_spinlock_count == 1,
2947686bcb5cSJeff Roberson 	    ("invalid count %d", curthread->td_md.md_spinlock_count));
2948ae7a6b38SJeff Roberson 	cpuid = PCPU_GET(cpuid);
2949018ff686SJeff Roberson 	tdq = TDQ_SELF();
2950686bcb5cSJeff Roberson 	TDQ_LOCK(tdq);
2951686bcb5cSJeff Roberson 	spinlock_exit();
2952ae7a6b38SJeff Roberson 	MPASS(td->td_lock == TDQ_LOCKPTR(tdq));
2953ae7a6b38SJeff Roberson 	td->td_oncpu = cpuid;
295428ef18b8SAndriy Gapon 	KTR_STATE1(KTR_SCHED, "thread", sched_tdname(td), "running",
295528ef18b8SAndriy Gapon 	    "prio:%d", td->td_priority);
295628ef18b8SAndriy Gapon 	SDT_PROBE0(sched, , , on__cpu);
29577b20fb19SJeff Roberson }
29587b20fb19SJeff Roberson 
29598f51ad55SJeff Roberson /*
29608f51ad55SJeff Roberson  * Create on first use to catch odd startup conditons.
29618f51ad55SJeff Roberson  */
29628f51ad55SJeff Roberson char *
29638f51ad55SJeff Roberson sched_tdname(struct thread *td)
29648f51ad55SJeff Roberson {
29658f51ad55SJeff Roberson #ifdef KTR
29668f51ad55SJeff Roberson 	struct td_sched *ts;
29678f51ad55SJeff Roberson 
296893ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
29698f51ad55SJeff Roberson 	if (ts->ts_name[0] == '\0')
29708f51ad55SJeff Roberson 		snprintf(ts->ts_name, sizeof(ts->ts_name),
29718f51ad55SJeff Roberson 		    "%s tid %d", td->td_name, td->td_tid);
29728f51ad55SJeff Roberson 	return (ts->ts_name);
29738f51ad55SJeff Roberson #else
29748f51ad55SJeff Roberson 	return (td->td_name);
29758f51ad55SJeff Roberson #endif
29768f51ad55SJeff Roberson }
29778f51ad55SJeff Roberson 
297844ad5475SJohn Baldwin #ifdef KTR
297944ad5475SJohn Baldwin void
298044ad5475SJohn Baldwin sched_clear_tdname(struct thread *td)
298144ad5475SJohn Baldwin {
298244ad5475SJohn Baldwin 	struct td_sched *ts;
298344ad5475SJohn Baldwin 
298493ccd6bfSKonstantin Belousov 	ts = td_get_sched(td);
298544ad5475SJohn Baldwin 	ts->ts_name[0] = '\0';
298644ad5475SJohn Baldwin }
298744ad5475SJohn Baldwin #endif
298844ad5475SJohn Baldwin 
298907095abfSIvan Voras #ifdef SMP
299007095abfSIvan Voras 
299107095abfSIvan Voras /*
299207095abfSIvan Voras  * Build the CPU topology dump string. Is recursively called to collect
299307095abfSIvan Voras  * the topology tree.
299407095abfSIvan Voras  */
299507095abfSIvan Voras static int
299607095abfSIvan Voras sysctl_kern_sched_topology_spec_internal(struct sbuf *sb, struct cpu_group *cg,
299707095abfSIvan Voras     int indent)
299807095abfSIvan Voras {
299971a19bdcSAttilio Rao 	char cpusetbuf[CPUSETBUFSIZ];
300007095abfSIvan Voras 	int i, first;
300107095abfSIvan Voras 
300207095abfSIvan Voras 	sbuf_printf(sb, "%*s<group level=\"%d\" cache-level=\"%d\">\n", indent,
300319b8a6dbSAndriy Gapon 	    "", 1 + indent / 2, cg->cg_level);
300471a19bdcSAttilio Rao 	sbuf_printf(sb, "%*s <cpu count=\"%d\" mask=\"%s\">", indent, "",
300571a19bdcSAttilio Rao 	    cg->cg_count, cpusetobj_strprint(cpusetbuf, &cg->cg_mask));
300607095abfSIvan Voras 	first = TRUE;
3007aefe0a8cSAlexander Motin 	for (i = cg->cg_first; i <= cg->cg_last; i++) {
300871a19bdcSAttilio Rao 		if (CPU_ISSET(i, &cg->cg_mask)) {
300907095abfSIvan Voras 			if (!first)
301007095abfSIvan Voras 				sbuf_printf(sb, ", ");
301107095abfSIvan Voras 			else
301207095abfSIvan Voras 				first = FALSE;
301307095abfSIvan Voras 			sbuf_printf(sb, "%d", i);
301407095abfSIvan Voras 		}
301507095abfSIvan Voras 	}
301607095abfSIvan Voras 	sbuf_printf(sb, "</cpu>\n");
301707095abfSIvan Voras 
301807095abfSIvan Voras 	if (cg->cg_flags != 0) {
3019611daf7eSIvan Voras 		sbuf_printf(sb, "%*s <flags>", indent, "");
302007095abfSIvan Voras 		if ((cg->cg_flags & CG_FLAG_HTT) != 0)
30215368befbSIvan Voras 			sbuf_printf(sb, "<flag name=\"HTT\">HTT group</flag>");
3022a401f2d0SIvan Voras 		if ((cg->cg_flags & CG_FLAG_THREAD) != 0)
3023a401f2d0SIvan Voras 			sbuf_printf(sb, "<flag name=\"THREAD\">THREAD group</flag>");
30247b55ab05SJeff Roberson 		if ((cg->cg_flags & CG_FLAG_SMT) != 0)
3025a401f2d0SIvan Voras 			sbuf_printf(sb, "<flag name=\"SMT\">SMT group</flag>");
302607095abfSIvan Voras 		sbuf_printf(sb, "</flags>\n");
3027611daf7eSIvan Voras 	}
302807095abfSIvan Voras 
302907095abfSIvan Voras 	if (cg->cg_children > 0) {
303007095abfSIvan Voras 		sbuf_printf(sb, "%*s <children>\n", indent, "");
303107095abfSIvan Voras 		for (i = 0; i < cg->cg_children; i++)
303207095abfSIvan Voras 			sysctl_kern_sched_topology_spec_internal(sb,
303307095abfSIvan Voras 			    &cg->cg_child[i], indent+2);
303407095abfSIvan Voras 		sbuf_printf(sb, "%*s </children>\n", indent, "");
303507095abfSIvan Voras 	}
303607095abfSIvan Voras 	sbuf_printf(sb, "%*s</group>\n", indent, "");
303707095abfSIvan Voras 	return (0);
303807095abfSIvan Voras }
303907095abfSIvan Voras 
304007095abfSIvan Voras /*
304107095abfSIvan Voras  * Sysctl handler for retrieving topology dump. It's a wrapper for
304207095abfSIvan Voras  * the recursive sysctl_kern_smp_topology_spec_internal().
304307095abfSIvan Voras  */
304407095abfSIvan Voras static int
304507095abfSIvan Voras sysctl_kern_sched_topology_spec(SYSCTL_HANDLER_ARGS)
304607095abfSIvan Voras {
304707095abfSIvan Voras 	struct sbuf *topo;
304807095abfSIvan Voras 	int err;
304907095abfSIvan Voras 
305007095abfSIvan Voras 	KASSERT(cpu_top != NULL, ("cpu_top isn't initialized"));
305107095abfSIvan Voras 
3052b97fa22cSIan Lepore 	topo = sbuf_new_for_sysctl(NULL, NULL, 512, req);
305307095abfSIvan Voras 	if (topo == NULL)
305407095abfSIvan Voras 		return (ENOMEM);
305507095abfSIvan Voras 
305607095abfSIvan Voras 	sbuf_printf(topo, "<groups>\n");
305707095abfSIvan Voras 	err = sysctl_kern_sched_topology_spec_internal(topo, cpu_top, 1);
305807095abfSIvan Voras 	sbuf_printf(topo, "</groups>\n");
305907095abfSIvan Voras 
306007095abfSIvan Voras 	if (err == 0) {
3061b97fa22cSIan Lepore 		err = sbuf_finish(topo);
306207095abfSIvan Voras 	}
306307095abfSIvan Voras 	sbuf_delete(topo);
306407095abfSIvan Voras 	return (err);
306507095abfSIvan Voras }
3066b67cc292SDavid Xu 
306707095abfSIvan Voras #endif
306807095abfSIvan Voras 
3069579895dfSAlexander Motin static int
3070579895dfSAlexander Motin sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
3071579895dfSAlexander Motin {
3072579895dfSAlexander Motin 	int error, new_val, period;
3073579895dfSAlexander Motin 
3074579895dfSAlexander Motin 	period = 1000000 / realstathz;
3075579895dfSAlexander Motin 	new_val = period * sched_slice;
3076579895dfSAlexander Motin 	error = sysctl_handle_int(oidp, &new_val, 0, req);
3077579895dfSAlexander Motin 	if (error != 0 || req->newptr == NULL)
3078579895dfSAlexander Motin 		return (error);
3079579895dfSAlexander Motin 	if (new_val <= 0)
3080579895dfSAlexander Motin 		return (EINVAL);
308137f4e025SAlexander Motin 	sched_slice = imax(1, (new_val + period / 2) / period);
30825e5c3873SJeff Roberson 	sched_slice_min = sched_slice / SCHED_SLICE_MIN_DIVISOR;
308337f4e025SAlexander Motin 	hogticks = imax(1, (2 * hz * sched_slice + realstathz / 2) /
308437f4e025SAlexander Motin 	    realstathz);
3085579895dfSAlexander Motin 	return (0);
3086579895dfSAlexander Motin }
3087579895dfSAlexander Motin 
30887029da5cSPawel Biernacki SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
30897029da5cSPawel Biernacki     "Scheduler");
3090ae7a6b38SJeff Roberson SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "ULE", 0,
3091e7d50326SJeff Roberson     "Scheduler name");
30927029da5cSPawel Biernacki SYSCTL_PROC(_kern_sched, OID_AUTO, quantum,
30937029da5cSPawel Biernacki     CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
30947029da5cSPawel Biernacki     sysctl_kern_quantum, "I",
309537f4e025SAlexander Motin     "Quantum for timeshare threads in microseconds");
3096ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice, CTLFLAG_RW, &sched_slice, 0,
309737f4e025SAlexander Motin     "Quantum for timeshare threads in stathz ticks");
3098ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, interact, CTLFLAG_RW, &sched_interact, 0,
3099ae7a6b38SJeff Roberson     "Interactivity score threshold");
310037f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, preempt_thresh, CTLFLAG_RW,
310137f4e025SAlexander Motin     &preempt_thresh, 0,
310237f4e025SAlexander Motin     "Maximal (lowest) priority for preemption");
310337f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, static_boost, CTLFLAG_RW, &static_boost, 0,
310437f4e025SAlexander Motin     "Assign static kernel priorities to sleeping threads");
310537f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, idlespins, CTLFLAG_RW, &sched_idlespins, 0,
310637f4e025SAlexander Motin     "Number of times idle thread will spin waiting for new work");
310737f4e025SAlexander Motin SYSCTL_INT(_kern_sched, OID_AUTO, idlespinthresh, CTLFLAG_RW,
310837f4e025SAlexander Motin     &sched_idlespinthresh, 0,
310937f4e025SAlexander Motin     "Threshold before we will permit idle thread spinning");
31107b8bfa0dSJeff Roberson #ifdef SMP
3111ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, affinity, CTLFLAG_RW, &affinity, 0,
3112ae7a6b38SJeff Roberson     "Number of hz ticks to keep thread affinity for");
3113ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, balance, CTLFLAG_RW, &rebalance, 0,
3114ae7a6b38SJeff Roberson     "Enables the long-term load balancer");
31157fcf154aSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, balance_interval, CTLFLAG_RW,
31167fcf154aSJeff Roberson     &balance_interval, 0,
3117579895dfSAlexander Motin     "Average period in stathz ticks to run the long-term balancer");
3118ae7a6b38SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, steal_idle, CTLFLAG_RW, &steal_idle, 0,
3119ae7a6b38SJeff Roberson     "Attempts to steal work from other cores before idling");
312028994a58SJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, steal_thresh, CTLFLAG_RW, &steal_thresh, 0,
312137f4e025SAlexander Motin     "Minimum load on remote CPU before we'll steal");
312297e9382dSDon Lewis SYSCTL_INT(_kern_sched, OID_AUTO, trysteal_limit, CTLFLAG_RW, &trysteal_limit,
312397e9382dSDon Lewis     0, "Topological distance limit for stealing threads in sched_switch()");
312497e9382dSDon Lewis SYSCTL_INT(_kern_sched, OID_AUTO, always_steal, CTLFLAG_RW, &always_steal, 0,
312597e9382dSDon Lewis     "Always run the stealer from the idle thread");
312607095abfSIvan Voras SYSCTL_PROC(_kern_sched, OID_AUTO, topology_spec, CTLTYPE_STRING |
3127c69a1a50SMateusz Guzik     CTLFLAG_MPSAFE | CTLFLAG_RD, NULL, 0, sysctl_kern_sched_topology_spec, "A",
312807095abfSIvan Voras     "XML dump of detected CPU topology");
31297b8bfa0dSJeff Roberson #endif
3130e7d50326SJeff Roberson 
313154b0e65fSJeff Roberson /* ps compat.  All cpu percentages from ULE are weighted. */
3132a5423ea3SJeff Roberson static int ccpu = 0;
3133b05ca429SPawel Biernacki SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0,
3134b05ca429SPawel Biernacki     "Decay factor used for updating %CPU in 4BSD scheduler");
3135