xref: /freebsd/sys/kern/sched_ule.c (revision 4b60e3242ee71bd3118653ab7ca66fe1ff94fdb4)
135e6168fSJeff Roberson /*-
215dc847eSJeff Roberson  * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org>
335e6168fSJeff Roberson  * All rights reserved.
435e6168fSJeff Roberson  *
535e6168fSJeff Roberson  * Redistribution and use in source and binary forms, with or without
635e6168fSJeff Roberson  * modification, are permitted provided that the following conditions
735e6168fSJeff Roberson  * are met:
835e6168fSJeff Roberson  * 1. Redistributions of source code must retain the above copyright
935e6168fSJeff Roberson  *    notice unmodified, this list of conditions, and the following
1035e6168fSJeff Roberson  *    disclaimer.
1135e6168fSJeff Roberson  * 2. Redistributions in binary form must reproduce the above copyright
1235e6168fSJeff Roberson  *    notice, this list of conditions and the following disclaimer in the
1335e6168fSJeff Roberson  *    documentation and/or other materials provided with the distribution.
1435e6168fSJeff Roberson  *
1535e6168fSJeff Roberson  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1635e6168fSJeff Roberson  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1735e6168fSJeff Roberson  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
1835e6168fSJeff Roberson  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
1935e6168fSJeff Roberson  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
2035e6168fSJeff Roberson  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2135e6168fSJeff Roberson  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2235e6168fSJeff Roberson  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2335e6168fSJeff Roberson  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
2435e6168fSJeff Roberson  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2535e6168fSJeff Roberson  */
2635e6168fSJeff Roberson 
27677b542eSDavid E. O'Brien #include <sys/cdefs.h>
28677b542eSDavid E. O'Brien __FBSDID("$FreeBSD$");
29677b542eSDavid E. O'Brien 
3035e6168fSJeff Roberson #include <sys/param.h>
3135e6168fSJeff Roberson #include <sys/systm.h>
3235e6168fSJeff Roberson #include <sys/kernel.h>
3335e6168fSJeff Roberson #include <sys/ktr.h>
3435e6168fSJeff Roberson #include <sys/lock.h>
3535e6168fSJeff Roberson #include <sys/mutex.h>
3635e6168fSJeff Roberson #include <sys/proc.h>
37245f3abfSJeff Roberson #include <sys/resource.h>
3835e6168fSJeff Roberson #include <sys/sched.h>
3935e6168fSJeff Roberson #include <sys/smp.h>
4035e6168fSJeff Roberson #include <sys/sx.h>
4135e6168fSJeff Roberson #include <sys/sysctl.h>
4235e6168fSJeff Roberson #include <sys/sysproto.h>
4335e6168fSJeff Roberson #include <sys/vmmeter.h>
4435e6168fSJeff Roberson #ifdef DDB
4535e6168fSJeff Roberson #include <ddb/ddb.h>
4635e6168fSJeff Roberson #endif
4735e6168fSJeff Roberson #ifdef KTRACE
4835e6168fSJeff Roberson #include <sys/uio.h>
4935e6168fSJeff Roberson #include <sys/ktrace.h>
5035e6168fSJeff Roberson #endif
5135e6168fSJeff Roberson 
5235e6168fSJeff Roberson #include <machine/cpu.h>
5335e6168fSJeff Roberson 
5415dc847eSJeff Roberson #define KTR_ULE         KTR_NFS
5515dc847eSJeff Roberson 
5635e6168fSJeff Roberson /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
5735e6168fSJeff Roberson /* XXX This is bogus compatability crap for ps */
5835e6168fSJeff Roberson static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
5935e6168fSJeff Roberson SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
6035e6168fSJeff Roberson 
6135e6168fSJeff Roberson static void sched_setup(void *dummy);
6235e6168fSJeff Roberson SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
6335e6168fSJeff Roberson 
6415dc847eSJeff Roberson static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED");
65e1f89c22SJeff Roberson 
6615dc847eSJeff Roberson static int sched_strict;
6715dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, "");
6815dc847eSJeff Roberson 
6915dc847eSJeff Roberson static int slice_min = 1;
7015dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, "");
7115dc847eSJeff Roberson 
72210491d3SJeff Roberson static int slice_max = 10;
7315dc847eSJeff Roberson SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, "");
7415dc847eSJeff Roberson 
7515dc847eSJeff Roberson int realstathz;
7615dc847eSJeff Roberson int tickincr = 1;
77783caefbSJeff Roberson 
78356500a3SJeff Roberson #ifdef SMP
79356500a3SJeff Roberson /* Callout to handle load balancing SMP systems. */
80356500a3SJeff Roberson static struct callout kseq_lb_callout;
81356500a3SJeff Roberson #endif
82356500a3SJeff Roberson 
8335e6168fSJeff Roberson /*
8435e6168fSJeff Roberson  * These datastructures are allocated within their parent datastructure but
8535e6168fSJeff Roberson  * are scheduler specific.
8635e6168fSJeff Roberson  */
8735e6168fSJeff Roberson 
8835e6168fSJeff Roberson struct ke_sched {
8935e6168fSJeff Roberson 	int		ske_slice;
9035e6168fSJeff Roberson 	struct runq	*ske_runq;
9135e6168fSJeff Roberson 	/* The following variables are only used for pctcpu calculation */
9235e6168fSJeff Roberson 	int		ske_ltick;	/* Last tick that we were running on */
9335e6168fSJeff Roberson 	int		ske_ftick;	/* First tick that we were running on */
9435e6168fSJeff Roberson 	int		ske_ticks;	/* Tick count */
9515dc847eSJeff Roberson 	/* CPU that we have affinity for. */
96cd6e33dfSJeff Roberson 	u_char		ske_cpu;
9735e6168fSJeff Roberson };
9835e6168fSJeff Roberson #define	ke_slice	ke_sched->ske_slice
9935e6168fSJeff Roberson #define	ke_runq		ke_sched->ske_runq
10035e6168fSJeff Roberson #define	ke_ltick	ke_sched->ske_ltick
10135e6168fSJeff Roberson #define	ke_ftick	ke_sched->ske_ftick
10235e6168fSJeff Roberson #define	ke_ticks	ke_sched->ske_ticks
103cd6e33dfSJeff Roberson #define	ke_cpu		ke_sched->ske_cpu
10435e6168fSJeff Roberson 
10535e6168fSJeff Roberson struct kg_sched {
106407b0157SJeff Roberson 	int	skg_slptime;		/* Number of ticks we vol. slept */
107407b0157SJeff Roberson 	int	skg_runtime;		/* Number of ticks we were running */
10835e6168fSJeff Roberson };
10935e6168fSJeff Roberson #define	kg_slptime	kg_sched->skg_slptime
110407b0157SJeff Roberson #define	kg_runtime	kg_sched->skg_runtime
11135e6168fSJeff Roberson 
11235e6168fSJeff Roberson struct td_sched {
11335e6168fSJeff Roberson 	int	std_slptime;
11435e6168fSJeff Roberson };
11535e6168fSJeff Roberson #define	td_slptime	td_sched->std_slptime
11635e6168fSJeff Roberson 
1175d7ef00cSJeff Roberson struct td_sched td_sched;
11835e6168fSJeff Roberson struct ke_sched ke_sched;
11935e6168fSJeff Roberson struct kg_sched kg_sched;
12035e6168fSJeff Roberson 
12135e6168fSJeff Roberson struct ke_sched *kse0_sched = &ke_sched;
12235e6168fSJeff Roberson struct kg_sched *ksegrp0_sched = &kg_sched;
12335e6168fSJeff Roberson struct p_sched *proc0_sched = NULL;
12435e6168fSJeff Roberson struct td_sched *thread0_sched = &td_sched;
12535e6168fSJeff Roberson 
12635e6168fSJeff Roberson /*
12735e6168fSJeff Roberson  * This priority range has 20 priorities on either end that are reachable
12835e6168fSJeff Roberson  * only through nice values.
129e1f89c22SJeff Roberson  *
130e1f89c22SJeff Roberson  * PRI_RANGE:	Total priority range for timeshare threads.
131e1f89c22SJeff Roberson  * PRI_NRESV:	Reserved priorities for nice.
132e1f89c22SJeff Roberson  * PRI_BASE:	The start of the dynamic range.
133e1f89c22SJeff Roberson  * DYN_RANGE:	Number of priorities that are available int the dynamic
134e1f89c22SJeff Roberson  *		priority range.
13535e6168fSJeff Roberson  */
136407b0157SJeff Roberson #define	SCHED_PRI_RANGE		(PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
137245f3abfSJeff Roberson #define	SCHED_PRI_NRESV		PRIO_TOTAL
13898c9b132SJeff Roberson #define	SCHED_PRI_NHALF		(PRIO_TOTAL / 2)
13915dc847eSJeff Roberson #define	SCHED_PRI_NTHRESH	(SCHED_PRI_NHALF - 1)
140e1f89c22SJeff Roberson #define	SCHED_PRI_BASE		((SCHED_PRI_NRESV / 2) + PRI_MIN_TIMESHARE)
141e1f89c22SJeff Roberson #define	SCHED_DYN_RANGE		(SCHED_PRI_RANGE - SCHED_PRI_NRESV)
14215dc847eSJeff Roberson #define	SCHED_PRI_INTERACT(score)					\
143210491d3SJeff Roberson     ((score) * SCHED_DYN_RANGE / SCHED_INTERACT_MAX)
14435e6168fSJeff Roberson 
14535e6168fSJeff Roberson /*
146e1f89c22SJeff Roberson  * These determine the interactivity of a process.
14735e6168fSJeff Roberson  *
148407b0157SJeff Roberson  * SLP_RUN_MAX:	Maximum amount of sleep time + run time we'll accumulate
149407b0157SJeff Roberson  *		before throttling back.
150e1f89c22SJeff Roberson  * SLP_RUN_THROTTLE:	Divisor for reducing slp/run time.
151210491d3SJeff Roberson  * INTERACT_MAX:	Maximum interactivity value.  Smaller is better.
152e1f89c22SJeff Roberson  * INTERACT_THRESH:	Threshhold for placement on the current runq.
15335e6168fSJeff Roberson  */
1544b60e324SJeff Roberson #define	SCHED_SLP_RUN_MAX	((hz * 2) << 10)
1553c124732SJeff Roberson #define	SCHED_SLP_RUN_THROTTLE	(2)
156210491d3SJeff Roberson #define	SCHED_INTERACT_MAX	(100)
157210491d3SJeff Roberson #define	SCHED_INTERACT_HALF	(SCHED_INTERACT_MAX / 2)
158210491d3SJeff Roberson #define	SCHED_INTERACT_THRESH	(20)
159e1f89c22SJeff Roberson 
16035e6168fSJeff Roberson /*
16135e6168fSJeff Roberson  * These parameters and macros determine the size of the time slice that is
16235e6168fSJeff Roberson  * granted to each thread.
16335e6168fSJeff Roberson  *
16435e6168fSJeff Roberson  * SLICE_MIN:	Minimum time slice granted, in units of ticks.
16535e6168fSJeff Roberson  * SLICE_MAX:	Maximum time slice granted.
16635e6168fSJeff Roberson  * SLICE_RANGE:	Range of available time slices scaled by hz.
167245f3abfSJeff Roberson  * SLICE_SCALE:	The number slices granted per val in the range of [0, max].
168245f3abfSJeff Roberson  * SLICE_NICE:  Determine the amount of slice granted to a scaled nice.
16935e6168fSJeff Roberson  */
17015dc847eSJeff Roberson #define	SCHED_SLICE_MIN			(slice_min)
17115dc847eSJeff Roberson #define	SCHED_SLICE_MAX			(slice_max)
17235e6168fSJeff Roberson #define	SCHED_SLICE_RANGE		(SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1)
17335e6168fSJeff Roberson #define	SCHED_SLICE_SCALE(val, max)	(((val) * SCHED_SLICE_RANGE) / (max))
174245f3abfSJeff Roberson #define	SCHED_SLICE_NICE(nice)						\
17515dc847eSJeff Roberson     (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_PRI_NTHRESH))
17635e6168fSJeff Roberson 
17735e6168fSJeff Roberson /*
17835e6168fSJeff Roberson  * This macro determines whether or not the kse belongs on the current or
17935e6168fSJeff Roberson  * next run queue.
180407b0157SJeff Roberson  *
181407b0157SJeff Roberson  * XXX nice value should effect how interactive a kg is.
18235e6168fSJeff Roberson  */
18315dc847eSJeff Roberson #define	SCHED_INTERACTIVE(kg)						\
18415dc847eSJeff Roberson     (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
185a5f099d0SJeff Roberson #define	SCHED_CURR(kg, ke)						\
18615dc847eSJeff Roberson     (ke->ke_thread->td_priority < PRI_MIN_TIMESHARE || SCHED_INTERACTIVE(kg))
18735e6168fSJeff Roberson 
18835e6168fSJeff Roberson /*
18935e6168fSJeff Roberson  * Cpu percentage computation macros and defines.
19035e6168fSJeff Roberson  *
19135e6168fSJeff Roberson  * SCHED_CPU_TIME:	Number of seconds to average the cpu usage across.
19235e6168fSJeff Roberson  * SCHED_CPU_TICKS:	Number of hz ticks to average the cpu usage across.
19335e6168fSJeff Roberson  */
19435e6168fSJeff Roberson 
1955053d272SJeff Roberson #define	SCHED_CPU_TIME	10
19635e6168fSJeff Roberson #define	SCHED_CPU_TICKS	(hz * SCHED_CPU_TIME)
19735e6168fSJeff Roberson 
19835e6168fSJeff Roberson /*
19915dc847eSJeff Roberson  * kseq - per processor runqs and statistics.
20035e6168fSJeff Roberson  */
20135e6168fSJeff Roberson 
20215dc847eSJeff Roberson #define	KSEQ_NCLASS	(PRI_IDLE + 1)	/* Number of run classes. */
20315dc847eSJeff Roberson 
20435e6168fSJeff Roberson struct kseq {
205a8949de2SJeff Roberson 	struct runq	ksq_idle;		/* Queue of IDLE threads. */
20615dc847eSJeff Roberson 	struct runq	ksq_timeshare[2];	/* Run queues for !IDLE. */
20715dc847eSJeff Roberson 	struct runq	*ksq_next;		/* Next timeshare queue. */
20815dc847eSJeff Roberson 	struct runq	*ksq_curr;		/* Current queue. */
20915dc847eSJeff Roberson 	int		ksq_loads[KSEQ_NCLASS];	/* Load for each class */
21015dc847eSJeff Roberson 	int		ksq_load;		/* Aggregate load. */
21115dc847eSJeff Roberson 	short		ksq_nice[PRIO_TOTAL + 1]; /* KSEs in each nice bin. */
21215dc847eSJeff Roberson 	short		ksq_nicemin;		/* Least nice. */
2135d7ef00cSJeff Roberson #ifdef SMP
2145d7ef00cSJeff Roberson 	unsigned int	ksq_rslices;	/* Slices on run queue */
2155d7ef00cSJeff Roberson #endif
21635e6168fSJeff Roberson };
21735e6168fSJeff Roberson 
21835e6168fSJeff Roberson /*
21935e6168fSJeff Roberson  * One kse queue per processor.
22035e6168fSJeff Roberson  */
2210a016a05SJeff Roberson #ifdef SMP
22235e6168fSJeff Roberson struct kseq	kseq_cpu[MAXCPU];
2230a016a05SJeff Roberson #define	KSEQ_SELF()	(&kseq_cpu[PCPU_GET(cpuid)])
2240a016a05SJeff Roberson #define	KSEQ_CPU(x)	(&kseq_cpu[(x)])
2250a016a05SJeff Roberson #else
2260a016a05SJeff Roberson struct kseq	kseq_cpu;
2270a016a05SJeff Roberson #define	KSEQ_SELF()	(&kseq_cpu)
2280a016a05SJeff Roberson #define	KSEQ_CPU(x)	(&kseq_cpu)
2290a016a05SJeff Roberson #endif
23035e6168fSJeff Roberson 
231245f3abfSJeff Roberson static void sched_slice(struct kse *ke);
23215dc847eSJeff Roberson static void sched_priority(struct ksegrp *kg);
233e1f89c22SJeff Roberson static int sched_interact_score(struct ksegrp *kg);
2344b60e324SJeff Roberson static void sched_interact_update(struct ksegrp *kg);
23535e6168fSJeff Roberson void sched_pctcpu_update(struct kse *ke);
23635e6168fSJeff Roberson int sched_pickcpu(void);
23735e6168fSJeff Roberson 
2385d7ef00cSJeff Roberson /* Operations on per processor queues */
2390a016a05SJeff Roberson static struct kse * kseq_choose(struct kseq *kseq);
2400a016a05SJeff Roberson static void kseq_setup(struct kseq *kseq);
241a8949de2SJeff Roberson static void kseq_add(struct kseq *kseq, struct kse *ke);
24215dc847eSJeff Roberson static void kseq_rem(struct kseq *kseq, struct kse *ke);
24315dc847eSJeff Roberson static void kseq_nice_add(struct kseq *kseq, int nice);
24415dc847eSJeff Roberson static void kseq_nice_rem(struct kseq *kseq, int nice);
2457cd650a9SJeff Roberson void kseq_print(int cpu);
2465d7ef00cSJeff Roberson #ifdef SMP
2475d7ef00cSJeff Roberson struct kseq * kseq_load_highest(void);
248356500a3SJeff Roberson void kseq_balance(void *arg);
249356500a3SJeff Roberson void kseq_move(struct kseq *from, int cpu);
2505d7ef00cSJeff Roberson #endif
2515d7ef00cSJeff Roberson 
25215dc847eSJeff Roberson void
2537cd650a9SJeff Roberson kseq_print(int cpu)
25415dc847eSJeff Roberson {
2557cd650a9SJeff Roberson 	struct kseq *kseq;
25615dc847eSJeff Roberson 	int i;
25715dc847eSJeff Roberson 
2587cd650a9SJeff Roberson 	kseq = KSEQ_CPU(cpu);
25915dc847eSJeff Roberson 
26015dc847eSJeff Roberson 	printf("kseq:\n");
26115dc847eSJeff Roberson 	printf("\tload:           %d\n", kseq->ksq_load);
26215dc847eSJeff Roberson 	printf("\tload ITHD:      %d\n", kseq->ksq_loads[PRI_ITHD]);
26315dc847eSJeff Roberson 	printf("\tload REALTIME:  %d\n", kseq->ksq_loads[PRI_REALTIME]);
26415dc847eSJeff Roberson 	printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]);
26515dc847eSJeff Roberson 	printf("\tload IDLE:      %d\n", kseq->ksq_loads[PRI_IDLE]);
26615dc847eSJeff Roberson 	printf("\tnicemin:\t%d\n", kseq->ksq_nicemin);
26715dc847eSJeff Roberson 	printf("\tnice counts:\n");
26815dc847eSJeff Roberson 	for (i = 0; i < PRIO_TOTAL + 1; i++)
26915dc847eSJeff Roberson 		if (kseq->ksq_nice[i])
27015dc847eSJeff Roberson 			printf("\t\t%d = %d\n",
27115dc847eSJeff Roberson 			    i - SCHED_PRI_NHALF, kseq->ksq_nice[i]);
27215dc847eSJeff Roberson }
27315dc847eSJeff Roberson 
274a8949de2SJeff Roberson static void
2755d7ef00cSJeff Roberson kseq_add(struct kseq *kseq, struct kse *ke)
2765d7ef00cSJeff Roberson {
277b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
278b5c4c4a7SJeff Roberson 	kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++;
27915dc847eSJeff Roberson 	kseq->ksq_load++;
28015dc847eSJeff Roberson 	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
28115dc847eSJeff Roberson 	CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))",
28215dc847eSJeff Roberson 	    ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority,
28315dc847eSJeff Roberson 	    ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin);
28415dc847eSJeff Roberson 	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
28515dc847eSJeff Roberson 		kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice);
2865d7ef00cSJeff Roberson #ifdef SMP
2875d7ef00cSJeff Roberson 	kseq->ksq_rslices += ke->ke_slice;
2885d7ef00cSJeff Roberson #endif
2895d7ef00cSJeff Roberson }
29015dc847eSJeff Roberson 
291a8949de2SJeff Roberson static void
2925d7ef00cSJeff Roberson kseq_rem(struct kseq *kseq, struct kse *ke)
2935d7ef00cSJeff Roberson {
294b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
295b5c4c4a7SJeff Roberson 	kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--;
29615dc847eSJeff Roberson 	kseq->ksq_load--;
29715dc847eSJeff Roberson 	ke->ke_runq = NULL;
29815dc847eSJeff Roberson 	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
29915dc847eSJeff Roberson 		kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice);
3005d7ef00cSJeff Roberson #ifdef SMP
3015d7ef00cSJeff Roberson 	kseq->ksq_rslices -= ke->ke_slice;
3025d7ef00cSJeff Roberson #endif
3035d7ef00cSJeff Roberson }
3045d7ef00cSJeff Roberson 
30515dc847eSJeff Roberson static void
30615dc847eSJeff Roberson kseq_nice_add(struct kseq *kseq, int nice)
30715dc847eSJeff Roberson {
308b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
30915dc847eSJeff Roberson 	/* Normalize to zero. */
31015dc847eSJeff Roberson 	kseq->ksq_nice[nice + SCHED_PRI_NHALF]++;
311b90816f1SJeff Roberson 	if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 1)
31215dc847eSJeff Roberson 		kseq->ksq_nicemin = nice;
31315dc847eSJeff Roberson }
31415dc847eSJeff Roberson 
31515dc847eSJeff Roberson static void
31615dc847eSJeff Roberson kseq_nice_rem(struct kseq *kseq, int nice)
31715dc847eSJeff Roberson {
31815dc847eSJeff Roberson 	int n;
31915dc847eSJeff Roberson 
320b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
32115dc847eSJeff Roberson 	/* Normalize to zero. */
32215dc847eSJeff Roberson 	n = nice + SCHED_PRI_NHALF;
32315dc847eSJeff Roberson 	kseq->ksq_nice[n]--;
32415dc847eSJeff Roberson 	KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count."));
32515dc847eSJeff Roberson 
32615dc847eSJeff Roberson 	/*
32715dc847eSJeff Roberson 	 * If this wasn't the smallest nice value or there are more in
32815dc847eSJeff Roberson 	 * this bucket we can just return.  Otherwise we have to recalculate
32915dc847eSJeff Roberson 	 * the smallest nice.
33015dc847eSJeff Roberson 	 */
33115dc847eSJeff Roberson 	if (nice != kseq->ksq_nicemin ||
33215dc847eSJeff Roberson 	    kseq->ksq_nice[n] != 0 ||
33315dc847eSJeff Roberson 	    kseq->ksq_loads[PRI_TIMESHARE] == 0)
33415dc847eSJeff Roberson 		return;
33515dc847eSJeff Roberson 
33615dc847eSJeff Roberson 	for (; n < SCHED_PRI_NRESV + 1; n++)
33715dc847eSJeff Roberson 		if (kseq->ksq_nice[n]) {
33815dc847eSJeff Roberson 			kseq->ksq_nicemin = n - SCHED_PRI_NHALF;
33915dc847eSJeff Roberson 			return;
34015dc847eSJeff Roberson 		}
34115dc847eSJeff Roberson }
34215dc847eSJeff Roberson 
3435d7ef00cSJeff Roberson #ifdef SMP
344356500a3SJeff Roberson /*
345356500a3SJeff Roberson  * kseq_balance is a simple CPU load balancing algorithm.  It operates by
346356500a3SJeff Roberson  * finding the least loaded and most loaded cpu and equalizing their load
347356500a3SJeff Roberson  * by migrating some processes.
348356500a3SJeff Roberson  *
349356500a3SJeff Roberson  * Dealing only with two CPUs at a time has two advantages.  Firstly, most
350356500a3SJeff Roberson  * installations will only have 2 cpus.  Secondly, load balancing too much at
351356500a3SJeff Roberson  * once can have an unpleasant effect on the system.  The scheduler rarely has
352356500a3SJeff Roberson  * enough information to make perfect decisions.  So this algorithm chooses
353356500a3SJeff Roberson  * algorithm simplicity and more gradual effects on load in larger systems.
354356500a3SJeff Roberson  *
355356500a3SJeff Roberson  * It could be improved by considering the priorities and slices assigned to
356356500a3SJeff Roberson  * each task prior to balancing them.  There are many pathological cases with
357356500a3SJeff Roberson  * any approach and so the semi random algorithm below may work as well as any.
358356500a3SJeff Roberson  *
359356500a3SJeff Roberson  */
360356500a3SJeff Roberson void
361356500a3SJeff Roberson kseq_balance(void *arg)
362356500a3SJeff Roberson {
363356500a3SJeff Roberson 	struct kseq *kseq;
364356500a3SJeff Roberson 	int high_load;
365356500a3SJeff Roberson 	int low_load;
366356500a3SJeff Roberson 	int high_cpu;
367356500a3SJeff Roberson 	int low_cpu;
368356500a3SJeff Roberson 	int move;
369356500a3SJeff Roberson 	int diff;
370356500a3SJeff Roberson 	int i;
371356500a3SJeff Roberson 
372356500a3SJeff Roberson 	high_cpu = 0;
373356500a3SJeff Roberson 	low_cpu = 0;
374356500a3SJeff Roberson 	high_load = 0;
375356500a3SJeff Roberson 	low_load = -1;
376356500a3SJeff Roberson 
377356500a3SJeff Roberson 	mtx_lock_spin(&sched_lock);
378356500a3SJeff Roberson 	for (i = 0; i < mp_maxid; i++) {
379356500a3SJeff Roberson 		if (CPU_ABSENT(i))
380356500a3SJeff Roberson 			continue;
381356500a3SJeff Roberson 		kseq = KSEQ_CPU(i);
382356500a3SJeff Roberson 		if (kseq->ksq_load > high_load) {
383356500a3SJeff Roberson 			high_load = kseq->ksq_load;
384356500a3SJeff Roberson 			high_cpu = i;
385356500a3SJeff Roberson 		}
386356500a3SJeff Roberson 		if (low_load == -1 || kseq->ksq_load < low_load) {
387356500a3SJeff Roberson 			low_load = kseq->ksq_load;
388356500a3SJeff Roberson 			low_cpu = i;
389356500a3SJeff Roberson 		}
390356500a3SJeff Roberson 	}
391356500a3SJeff Roberson 
392356500a3SJeff Roberson 	/*
393356500a3SJeff Roberson 	 * Nothing to do.
394356500a3SJeff Roberson 	 */
395356500a3SJeff Roberson 	if (high_load < 2 || low_load == high_load)
396356500a3SJeff Roberson 		goto out;
397356500a3SJeff Roberson 
398356500a3SJeff Roberson 	diff = high_load - low_load;
399356500a3SJeff Roberson 	move = diff / 2;
400356500a3SJeff Roberson 	if (diff & 0x1)
401356500a3SJeff Roberson 		move++;
402356500a3SJeff Roberson 
403356500a3SJeff Roberson 	for (i = 0; i < move; i++)
404356500a3SJeff Roberson 		kseq_move(KSEQ_CPU(high_cpu), low_cpu);
405356500a3SJeff Roberson 
406356500a3SJeff Roberson out:
407356500a3SJeff Roberson 	mtx_unlock_spin(&sched_lock);
408356500a3SJeff Roberson 	callout_reset(&kseq_lb_callout, hz, kseq_balance, NULL);
409356500a3SJeff Roberson 
410356500a3SJeff Roberson 	return;
411356500a3SJeff Roberson }
412356500a3SJeff Roberson 
4135d7ef00cSJeff Roberson struct kseq *
4145d7ef00cSJeff Roberson kseq_load_highest(void)
4155d7ef00cSJeff Roberson {
4165d7ef00cSJeff Roberson 	struct kseq *kseq;
4175d7ef00cSJeff Roberson 	int load;
4185d7ef00cSJeff Roberson 	int cpu;
4195d7ef00cSJeff Roberson 	int i;
4205d7ef00cSJeff Roberson 
421b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
4225d7ef00cSJeff Roberson 	cpu = 0;
4235d7ef00cSJeff Roberson 	load = 0;
4245d7ef00cSJeff Roberson 
4255d7ef00cSJeff Roberson 	for (i = 0; i < mp_maxid; i++) {
4265d7ef00cSJeff Roberson 		if (CPU_ABSENT(i))
4275d7ef00cSJeff Roberson 			continue;
4285d7ef00cSJeff Roberson 		kseq = KSEQ_CPU(i);
42915dc847eSJeff Roberson 		if (kseq->ksq_load > load) {
43015dc847eSJeff Roberson 			load = kseq->ksq_load;
4315d7ef00cSJeff Roberson 			cpu = i;
4325d7ef00cSJeff Roberson 		}
4335d7ef00cSJeff Roberson 	}
43458177de2SJeff Roberson 	if (load > 1)
4355d7ef00cSJeff Roberson 		return (KSEQ_CPU(cpu));
4365d7ef00cSJeff Roberson 
4375d7ef00cSJeff Roberson 	return (NULL);
4385d7ef00cSJeff Roberson }
439356500a3SJeff Roberson 
440356500a3SJeff Roberson void
441356500a3SJeff Roberson kseq_move(struct kseq *from, int cpu)
442356500a3SJeff Roberson {
443356500a3SJeff Roberson 	struct kse *ke;
444356500a3SJeff Roberson 
445356500a3SJeff Roberson 	ke = kseq_choose(from);
446356500a3SJeff Roberson 	runq_remove(ke->ke_runq, ke);
447356500a3SJeff Roberson 	ke->ke_state = KES_THREAD;
448356500a3SJeff Roberson 	kseq_rem(from, ke);
449356500a3SJeff Roberson 
450356500a3SJeff Roberson 	ke->ke_cpu = cpu;
451356500a3SJeff Roberson 	sched_add(ke);
452356500a3SJeff Roberson }
4535d7ef00cSJeff Roberson #endif
4545d7ef00cSJeff Roberson 
4555d7ef00cSJeff Roberson struct kse *
4565d7ef00cSJeff Roberson kseq_choose(struct kseq *kseq)
4575d7ef00cSJeff Roberson {
4585d7ef00cSJeff Roberson 	struct kse *ke;
4595d7ef00cSJeff Roberson 	struct runq *swap;
4605d7ef00cSJeff Roberson 
461b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
46215dc847eSJeff Roberson 	swap = NULL;
463a8949de2SJeff Roberson 
46415dc847eSJeff Roberson 	for (;;) {
46515dc847eSJeff Roberson 		ke = runq_choose(kseq->ksq_curr);
46615dc847eSJeff Roberson 		if (ke == NULL) {
46715dc847eSJeff Roberson 			/*
46815dc847eSJeff Roberson 			 * We already swaped once and didn't get anywhere.
46915dc847eSJeff Roberson 			 */
47015dc847eSJeff Roberson 			if (swap)
47115dc847eSJeff Roberson 				break;
4725d7ef00cSJeff Roberson 			swap = kseq->ksq_curr;
4735d7ef00cSJeff Roberson 			kseq->ksq_curr = kseq->ksq_next;
4745d7ef00cSJeff Roberson 			kseq->ksq_next = swap;
47515dc847eSJeff Roberson 			continue;
476a8949de2SJeff Roberson 		}
47715dc847eSJeff Roberson 		/*
47815dc847eSJeff Roberson 		 * If we encounter a slice of 0 the kse is in a
47915dc847eSJeff Roberson 		 * TIMESHARE kse group and its nice was too far out
48015dc847eSJeff Roberson 		 * of the range that receives slices.
48115dc847eSJeff Roberson 		 */
48215dc847eSJeff Roberson 		if (ke->ke_slice == 0) {
48315dc847eSJeff Roberson 			runq_remove(ke->ke_runq, ke);
48415dc847eSJeff Roberson 			sched_slice(ke);
48515dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_next;
48615dc847eSJeff Roberson 			runq_add(ke->ke_runq, ke);
48715dc847eSJeff Roberson 			continue;
48815dc847eSJeff Roberson 		}
48915dc847eSJeff Roberson 		return (ke);
49015dc847eSJeff Roberson 	}
49115dc847eSJeff Roberson 
492a8949de2SJeff Roberson 	return (runq_choose(&kseq->ksq_idle));
493245f3abfSJeff Roberson }
4940a016a05SJeff Roberson 
4950a016a05SJeff Roberson static void
4960a016a05SJeff Roberson kseq_setup(struct kseq *kseq)
4970a016a05SJeff Roberson {
49815dc847eSJeff Roberson 	runq_init(&kseq->ksq_timeshare[0]);
49915dc847eSJeff Roberson 	runq_init(&kseq->ksq_timeshare[1]);
500a8949de2SJeff Roberson 	runq_init(&kseq->ksq_idle);
50115dc847eSJeff Roberson 
50215dc847eSJeff Roberson 	kseq->ksq_curr = &kseq->ksq_timeshare[0];
50315dc847eSJeff Roberson 	kseq->ksq_next = &kseq->ksq_timeshare[1];
50415dc847eSJeff Roberson 
50515dc847eSJeff Roberson 	kseq->ksq_loads[PRI_ITHD] = 0;
50615dc847eSJeff Roberson 	kseq->ksq_loads[PRI_REALTIME] = 0;
50715dc847eSJeff Roberson 	kseq->ksq_loads[PRI_TIMESHARE] = 0;
50815dc847eSJeff Roberson 	kseq->ksq_loads[PRI_IDLE] = 0;
5097cd650a9SJeff Roberson 	kseq->ksq_load = 0;
5105d7ef00cSJeff Roberson #ifdef SMP
5115d7ef00cSJeff Roberson 	kseq->ksq_rslices = 0;
5125d7ef00cSJeff Roberson #endif
5130a016a05SJeff Roberson }
5140a016a05SJeff Roberson 
51535e6168fSJeff Roberson static void
51635e6168fSJeff Roberson sched_setup(void *dummy)
51735e6168fSJeff Roberson {
51835e6168fSJeff Roberson 	int i;
51935e6168fSJeff Roberson 
52015dc847eSJeff Roberson 	slice_min = (hz/100);
52115dc847eSJeff Roberson 	slice_max = (hz/10);
522e1f89c22SJeff Roberson 
52335e6168fSJeff Roberson 	mtx_lock_spin(&sched_lock);
52435e6168fSJeff Roberson 	/* init kseqs */
5250a016a05SJeff Roberson 	for (i = 0; i < MAXCPU; i++)
5260a016a05SJeff Roberson 		kseq_setup(KSEQ_CPU(i));
52715dc847eSJeff Roberson 
52815dc847eSJeff Roberson 	kseq_add(KSEQ_SELF(), &kse0);
52935e6168fSJeff Roberson 	mtx_unlock_spin(&sched_lock);
530356500a3SJeff Roberson #ifdef SMP
531356500a3SJeff Roberson 	callout_init(&kseq_lb_callout, 1);
532356500a3SJeff Roberson 	kseq_balance(NULL);
533356500a3SJeff Roberson #endif
53435e6168fSJeff Roberson }
53535e6168fSJeff Roberson 
53635e6168fSJeff Roberson /*
53735e6168fSJeff Roberson  * Scale the scheduling priority according to the "interactivity" of this
53835e6168fSJeff Roberson  * process.
53935e6168fSJeff Roberson  */
54015dc847eSJeff Roberson static void
54135e6168fSJeff Roberson sched_priority(struct ksegrp *kg)
54235e6168fSJeff Roberson {
54335e6168fSJeff Roberson 	int pri;
54435e6168fSJeff Roberson 
54535e6168fSJeff Roberson 	if (kg->kg_pri_class != PRI_TIMESHARE)
54615dc847eSJeff Roberson 		return;
54735e6168fSJeff Roberson 
54815dc847eSJeff Roberson 	pri = SCHED_PRI_INTERACT(sched_interact_score(kg));
549e1f89c22SJeff Roberson 	pri += SCHED_PRI_BASE;
55035e6168fSJeff Roberson 	pri += kg->kg_nice;
55135e6168fSJeff Roberson 
55235e6168fSJeff Roberson 	if (pri > PRI_MAX_TIMESHARE)
55335e6168fSJeff Roberson 		pri = PRI_MAX_TIMESHARE;
55435e6168fSJeff Roberson 	else if (pri < PRI_MIN_TIMESHARE)
55535e6168fSJeff Roberson 		pri = PRI_MIN_TIMESHARE;
55635e6168fSJeff Roberson 
55735e6168fSJeff Roberson 	kg->kg_user_pri = pri;
55835e6168fSJeff Roberson 
55915dc847eSJeff Roberson 	return;
56035e6168fSJeff Roberson }
56135e6168fSJeff Roberson 
56235e6168fSJeff Roberson /*
563245f3abfSJeff Roberson  * Calculate a time slice based on the properties of the kseg and the runq
564a8949de2SJeff Roberson  * that we're on.  This is only for PRI_TIMESHARE ksegrps.
56535e6168fSJeff Roberson  */
566245f3abfSJeff Roberson static void
567245f3abfSJeff Roberson sched_slice(struct kse *ke)
56835e6168fSJeff Roberson {
56915dc847eSJeff Roberson 	struct kseq *kseq;
570245f3abfSJeff Roberson 	struct ksegrp *kg;
57135e6168fSJeff Roberson 
572245f3abfSJeff Roberson 	kg = ke->ke_ksegrp;
57315dc847eSJeff Roberson 	kseq = KSEQ_CPU(ke->ke_cpu);
57435e6168fSJeff Roberson 
575245f3abfSJeff Roberson 	/*
576245f3abfSJeff Roberson 	 * Rationale:
577245f3abfSJeff Roberson 	 * KSEs in interactive ksegs get the minimum slice so that we
578245f3abfSJeff Roberson 	 * quickly notice if it abuses its advantage.
579245f3abfSJeff Roberson 	 *
580245f3abfSJeff Roberson 	 * KSEs in non-interactive ksegs are assigned a slice that is
581245f3abfSJeff Roberson 	 * based on the ksegs nice value relative to the least nice kseg
582245f3abfSJeff Roberson 	 * on the run queue for this cpu.
583245f3abfSJeff Roberson 	 *
584245f3abfSJeff Roberson 	 * If the KSE is less nice than all others it gets the maximum
585245f3abfSJeff Roberson 	 * slice and other KSEs will adjust their slice relative to
586245f3abfSJeff Roberson 	 * this when they first expire.
587245f3abfSJeff Roberson 	 *
588245f3abfSJeff Roberson 	 * There is 20 point window that starts relative to the least
589245f3abfSJeff Roberson 	 * nice kse on the run queue.  Slice size is determined by
590245f3abfSJeff Roberson 	 * the kse distance from the last nice ksegrp.
591245f3abfSJeff Roberson 	 *
592245f3abfSJeff Roberson 	 * If you are outside of the window you will get no slice and
593245f3abfSJeff Roberson 	 * you will be reevaluated each time you are selected on the
594245f3abfSJeff Roberson 	 * run queue.
595245f3abfSJeff Roberson 	 *
596245f3abfSJeff Roberson 	 */
597245f3abfSJeff Roberson 
59815dc847eSJeff Roberson 	if (!SCHED_INTERACTIVE(kg)) {
599245f3abfSJeff Roberson 		int nice;
600245f3abfSJeff Roberson 
60115dc847eSJeff Roberson 		nice = kg->kg_nice + (0 - kseq->ksq_nicemin);
60215dc847eSJeff Roberson 		if (kseq->ksq_loads[PRI_TIMESHARE] == 0 ||
60315dc847eSJeff Roberson 		    kg->kg_nice < kseq->ksq_nicemin)
604245f3abfSJeff Roberson 			ke->ke_slice = SCHED_SLICE_MAX;
60515dc847eSJeff Roberson 		else if (nice <= SCHED_PRI_NTHRESH)
606245f3abfSJeff Roberson 			ke->ke_slice = SCHED_SLICE_NICE(nice);
607245f3abfSJeff Roberson 		else
608245f3abfSJeff Roberson 			ke->ke_slice = 0;
609245f3abfSJeff Roberson 	} else
610245f3abfSJeff Roberson 		ke->ke_slice = SCHED_SLICE_MIN;
61135e6168fSJeff Roberson 
61215dc847eSJeff Roberson 	CTR6(KTR_ULE,
61315dc847eSJeff Roberson 	    "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)",
61415dc847eSJeff Roberson 	    ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin,
61515dc847eSJeff Roberson 	    kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg));
61615dc847eSJeff Roberson 
617407b0157SJeff Roberson 	/*
618a8949de2SJeff Roberson 	 * Check to see if we need to scale back the slp and run time
619a8949de2SJeff Roberson 	 * in the kg.  This will cause us to forget old interactivity
620a8949de2SJeff Roberson 	 * while maintaining the current ratio.
621407b0157SJeff Roberson 	 */
6224b60e324SJeff Roberson 	sched_interact_update(kg);
623407b0157SJeff Roberson 
624245f3abfSJeff Roberson 	return;
62535e6168fSJeff Roberson }
62635e6168fSJeff Roberson 
6274b60e324SJeff Roberson static void
6284b60e324SJeff Roberson sched_interact_update(struct ksegrp *kg)
6294b60e324SJeff Roberson {
6304b60e324SJeff Roberson 	if ((kg->kg_runtime + kg->kg_slptime) >  SCHED_SLP_RUN_MAX) {
6314b60e324SJeff Roberson 		kg->kg_runtime = (kg->kg_runtime / 5) * 4;
6324b60e324SJeff Roberson 		kg->kg_slptime = (kg->kg_slptime / 5) * 4;
6334b60e324SJeff Roberson 	}
6344b60e324SJeff Roberson }
6354b60e324SJeff Roberson 
636e1f89c22SJeff Roberson static int
637e1f89c22SJeff Roberson sched_interact_score(struct ksegrp *kg)
638e1f89c22SJeff Roberson {
639210491d3SJeff Roberson 	int div;
640e1f89c22SJeff Roberson 
641e1f89c22SJeff Roberson 	if (kg->kg_runtime > kg->kg_slptime) {
642210491d3SJeff Roberson 		div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF);
643210491d3SJeff Roberson 		return (SCHED_INTERACT_HALF +
644210491d3SJeff Roberson 		    (SCHED_INTERACT_HALF - (kg->kg_slptime / div)));
645210491d3SJeff Roberson 	} if (kg->kg_slptime > kg->kg_runtime) {
646210491d3SJeff Roberson 		div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF);
647210491d3SJeff Roberson 		return (kg->kg_runtime / div);
648e1f89c22SJeff Roberson 	}
649e1f89c22SJeff Roberson 
650210491d3SJeff Roberson 	/*
651210491d3SJeff Roberson 	 * This can happen if slptime and runtime are 0.
652210491d3SJeff Roberson 	 */
653210491d3SJeff Roberson 	return (0);
654e1f89c22SJeff Roberson 
655e1f89c22SJeff Roberson }
656e1f89c22SJeff Roberson 
65715dc847eSJeff Roberson /*
65815dc847eSJeff Roberson  * This is only somewhat accurate since given many processes of the same
65915dc847eSJeff Roberson  * priority they will switch when their slices run out, which will be
66015dc847eSJeff Roberson  * at most SCHED_SLICE_MAX.
66115dc847eSJeff Roberson  */
66235e6168fSJeff Roberson int
66335e6168fSJeff Roberson sched_rr_interval(void)
66435e6168fSJeff Roberson {
66535e6168fSJeff Roberson 	return (SCHED_SLICE_MAX);
66635e6168fSJeff Roberson }
66735e6168fSJeff Roberson 
66835e6168fSJeff Roberson void
66935e6168fSJeff Roberson sched_pctcpu_update(struct kse *ke)
67035e6168fSJeff Roberson {
67135e6168fSJeff Roberson 	/*
67235e6168fSJeff Roberson 	 * Adjust counters and watermark for pctcpu calc.
673210491d3SJeff Roberson 	 */
674210491d3SJeff Roberson 
675210491d3SJeff Roberson 	/*
67665c8760dSJeff Roberson 	 * Shift the tick count out so that the divide doesn't round away
67765c8760dSJeff Roberson 	 * our results.
67865c8760dSJeff Roberson 	 */
67965c8760dSJeff Roberson 	ke->ke_ticks <<= 10;
68035e6168fSJeff Roberson 	ke->ke_ticks = (ke->ke_ticks / (ke->ke_ltick - ke->ke_ftick)) *
68135e6168fSJeff Roberson 		    SCHED_CPU_TICKS;
68265c8760dSJeff Roberson 	ke->ke_ticks >>= 10;
68335e6168fSJeff Roberson 	ke->ke_ltick = ticks;
68435e6168fSJeff Roberson 	ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS;
68535e6168fSJeff Roberson }
68635e6168fSJeff Roberson 
68735e6168fSJeff Roberson #ifdef SMP
6885d7ef00cSJeff Roberson /* XXX Should be changed to kseq_load_lowest() */
68935e6168fSJeff Roberson int
69035e6168fSJeff Roberson sched_pickcpu(void)
69135e6168fSJeff Roberson {
6920a016a05SJeff Roberson 	struct kseq *kseq;
69335e6168fSJeff Roberson 	int load;
6940a016a05SJeff Roberson 	int cpu;
69535e6168fSJeff Roberson 	int i;
69635e6168fSJeff Roberson 
697b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
69835e6168fSJeff Roberson 	if (!smp_started)
69935e6168fSJeff Roberson 		return (0);
70035e6168fSJeff Roberson 
7010a016a05SJeff Roberson 	load = 0;
7020a016a05SJeff Roberson 	cpu = 0;
70335e6168fSJeff Roberson 
70435e6168fSJeff Roberson 	for (i = 0; i < mp_maxid; i++) {
70535e6168fSJeff Roberson 		if (CPU_ABSENT(i))
70635e6168fSJeff Roberson 			continue;
7070a016a05SJeff Roberson 		kseq = KSEQ_CPU(i);
70815dc847eSJeff Roberson 		if (kseq->ksq_load < load) {
70935e6168fSJeff Roberson 			cpu = i;
71015dc847eSJeff Roberson 			load = kseq->ksq_load;
71135e6168fSJeff Roberson 		}
71235e6168fSJeff Roberson 	}
71335e6168fSJeff Roberson 
71435e6168fSJeff Roberson 	CTR1(KTR_RUNQ, "sched_pickcpu: %d", cpu);
71535e6168fSJeff Roberson 	return (cpu);
71635e6168fSJeff Roberson }
71735e6168fSJeff Roberson #else
71835e6168fSJeff Roberson int
71935e6168fSJeff Roberson sched_pickcpu(void)
72035e6168fSJeff Roberson {
72135e6168fSJeff Roberson 	return (0);
72235e6168fSJeff Roberson }
72335e6168fSJeff Roberson #endif
72435e6168fSJeff Roberson 
72535e6168fSJeff Roberson void
72635e6168fSJeff Roberson sched_prio(struct thread *td, u_char prio)
72735e6168fSJeff Roberson {
72835e6168fSJeff Roberson 	struct kse *ke;
72935e6168fSJeff Roberson 	struct runq *rq;
73035e6168fSJeff Roberson 
73135e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
73235e6168fSJeff Roberson 	ke = td->td_kse;
73335e6168fSJeff Roberson 	td->td_priority = prio;
73435e6168fSJeff Roberson 
73535e6168fSJeff Roberson 	if (TD_ON_RUNQ(td)) {
73635e6168fSJeff Roberson 		rq = ke->ke_runq;
73735e6168fSJeff Roberson 
73835e6168fSJeff Roberson 		runq_remove(rq, ke);
73935e6168fSJeff Roberson 		runq_add(rq, ke);
74035e6168fSJeff Roberson 	}
74135e6168fSJeff Roberson }
74235e6168fSJeff Roberson 
74335e6168fSJeff Roberson void
74435e6168fSJeff Roberson sched_switchout(struct thread *td)
74535e6168fSJeff Roberson {
74635e6168fSJeff Roberson 	struct kse *ke;
74735e6168fSJeff Roberson 
74835e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
74935e6168fSJeff Roberson 
75035e6168fSJeff Roberson 	ke = td->td_kse;
75135e6168fSJeff Roberson 
75235e6168fSJeff Roberson 	td->td_last_kse = ke;
753060563ecSJulian Elischer         td->td_lastcpu = td->td_oncpu;
754060563ecSJulian Elischer 	td->td_oncpu = NOCPU;
7554a338afdSJulian Elischer         td->td_flags &= ~TDF_NEEDRESCHED;
75635e6168fSJeff Roberson 
75735e6168fSJeff Roberson 	if (TD_IS_RUNNING(td)) {
758210491d3SJeff Roberson 		/*
759210491d3SJeff Roberson 		 * This queue is always correct except for idle threads which
760210491d3SJeff Roberson 		 * have a higher priority due to priority propagation.
761210491d3SJeff Roberson 		 */
762210491d3SJeff Roberson 		if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE &&
763210491d3SJeff Roberson 		    ke->ke_thread->td_priority > PRI_MIN_IDLE)
764210491d3SJeff Roberson 			ke->ke_runq = KSEQ_SELF()->ksq_curr;
76515dc847eSJeff Roberson 		runq_add(ke->ke_runq, ke);
76615dc847eSJeff Roberson 		/* setrunqueue(td); */
76735e6168fSJeff Roberson 		return;
768e1f89c22SJeff Roberson 	}
76915dc847eSJeff Roberson 	if (ke->ke_runq)
77015dc847eSJeff Roberson 		kseq_rem(KSEQ_CPU(ke->ke_cpu), ke);
77135e6168fSJeff Roberson 	/*
77235e6168fSJeff Roberson 	 * We will not be on the run queue. So we must be
77335e6168fSJeff Roberson 	 * sleeping or similar.
77435e6168fSJeff Roberson 	 */
7750e2a4d3aSDavid Xu 	if (td->td_proc->p_flag & P_SA)
77635e6168fSJeff Roberson 		kse_reassign(ke);
77735e6168fSJeff Roberson }
77835e6168fSJeff Roberson 
77935e6168fSJeff Roberson void
78035e6168fSJeff Roberson sched_switchin(struct thread *td)
78135e6168fSJeff Roberson {
78235e6168fSJeff Roberson 	/* struct kse *ke = td->td_kse; */
78335e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
78435e6168fSJeff Roberson 
785060563ecSJulian Elischer 	td->td_oncpu = PCPU_GET(cpuid);
78635e6168fSJeff Roberson }
78735e6168fSJeff Roberson 
78835e6168fSJeff Roberson void
78935e6168fSJeff Roberson sched_nice(struct ksegrp *kg, int nice)
79035e6168fSJeff Roberson {
79115dc847eSJeff Roberson 	struct kse *ke;
79235e6168fSJeff Roberson 	struct thread *td;
79315dc847eSJeff Roberson 	struct kseq *kseq;
79435e6168fSJeff Roberson 
7950b5318c8SJohn Baldwin 	PROC_LOCK_ASSERT(kg->kg_proc, MA_OWNED);
7960b5318c8SJohn Baldwin 	mtx_assert(&sched_lock, MA_OWNED);
79715dc847eSJeff Roberson 	/*
79815dc847eSJeff Roberson 	 * We need to adjust the nice counts for running KSEs.
79915dc847eSJeff Roberson 	 */
80015dc847eSJeff Roberson 	if (kg->kg_pri_class == PRI_TIMESHARE)
80115dc847eSJeff Roberson 		FOREACH_KSE_IN_GROUP(kg, ke) {
80215dc847eSJeff Roberson 			if (ke->ke_state != KES_ONRUNQ &&
80315dc847eSJeff Roberson 			    ke->ke_state != KES_THREAD)
80415dc847eSJeff Roberson 				continue;
80515dc847eSJeff Roberson 			kseq = KSEQ_CPU(ke->ke_cpu);
80615dc847eSJeff Roberson 			kseq_nice_rem(kseq, kg->kg_nice);
80715dc847eSJeff Roberson 			kseq_nice_add(kseq, nice);
80815dc847eSJeff Roberson 		}
80935e6168fSJeff Roberson 	kg->kg_nice = nice;
81035e6168fSJeff Roberson 	sched_priority(kg);
81115dc847eSJeff Roberson 	FOREACH_THREAD_IN_GROUP(kg, td)
8124a338afdSJulian Elischer 		td->td_flags |= TDF_NEEDRESCHED;
81335e6168fSJeff Roberson }
81435e6168fSJeff Roberson 
81535e6168fSJeff Roberson void
81635e6168fSJeff Roberson sched_sleep(struct thread *td, u_char prio)
81735e6168fSJeff Roberson {
81835e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
81935e6168fSJeff Roberson 
82035e6168fSJeff Roberson 	td->td_slptime = ticks;
82135e6168fSJeff Roberson 	td->td_priority = prio;
82235e6168fSJeff Roberson 
82315dc847eSJeff Roberson 	CTR2(KTR_ULE, "sleep kse %p (tick: %d)",
82415dc847eSJeff Roberson 	    td->td_kse, td->td_slptime);
82535e6168fSJeff Roberson }
82635e6168fSJeff Roberson 
82735e6168fSJeff Roberson void
82835e6168fSJeff Roberson sched_wakeup(struct thread *td)
82935e6168fSJeff Roberson {
83035e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
83135e6168fSJeff Roberson 
83235e6168fSJeff Roberson 	/*
83335e6168fSJeff Roberson 	 * Let the kseg know how long we slept for.  This is because process
83435e6168fSJeff Roberson 	 * interactivity behavior is modeled in the kseg.
83535e6168fSJeff Roberson 	 */
83635e6168fSJeff Roberson 	if (td->td_slptime) {
837f1e8dc4aSJeff Roberson 		struct ksegrp *kg;
83815dc847eSJeff Roberson 		int hzticks;
839f1e8dc4aSJeff Roberson 
840f1e8dc4aSJeff Roberson 		kg = td->td_ksegrp;
84115dc847eSJeff Roberson 		hzticks = ticks - td->td_slptime;
84215dc847eSJeff Roberson 		kg->kg_slptime += hzticks << 10;
8434b60e324SJeff Roberson 		sched_interact_update(kg);
844f1e8dc4aSJeff Roberson 		sched_priority(kg);
8454b60e324SJeff Roberson 		if (td->td_kse)
8464b60e324SJeff Roberson 			sched_slice(td->td_kse);
84715dc847eSJeff Roberson 		CTR2(KTR_ULE, "wakeup kse %p (%d ticks)",
84815dc847eSJeff Roberson 		    td->td_kse, hzticks);
84935e6168fSJeff Roberson 		td->td_slptime = 0;
850f1e8dc4aSJeff Roberson 	}
85135e6168fSJeff Roberson 	setrunqueue(td);
85235e6168fSJeff Roberson         if (td->td_priority < curthread->td_priority)
8534a338afdSJulian Elischer                 curthread->td_flags |= TDF_NEEDRESCHED;
85435e6168fSJeff Roberson }
85535e6168fSJeff Roberson 
85635e6168fSJeff Roberson /*
85735e6168fSJeff Roberson  * Penalize the parent for creating a new child and initialize the child's
85835e6168fSJeff Roberson  * priority.
85935e6168fSJeff Roberson  */
86035e6168fSJeff Roberson void
86115dc847eSJeff Roberson sched_fork(struct proc *p, struct proc *p1)
86235e6168fSJeff Roberson {
86335e6168fSJeff Roberson 
86435e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
86535e6168fSJeff Roberson 
86615dc847eSJeff Roberson 	sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1));
86715dc847eSJeff Roberson 	sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1));
86815dc847eSJeff Roberson 	sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1));
86915dc847eSJeff Roberson }
87015dc847eSJeff Roberson 
87115dc847eSJeff Roberson void
87215dc847eSJeff Roberson sched_fork_kse(struct kse *ke, struct kse *child)
87315dc847eSJeff Roberson {
8742056d0a1SJohn Baldwin 
875210491d3SJeff Roberson 	child->ke_slice = 1;	/* Attempt to quickly learn interactivity. */
87615dc847eSJeff Roberson 	child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */
87715dc847eSJeff Roberson 	child->ke_runq = NULL;
87815dc847eSJeff Roberson 
87915dc847eSJeff Roberson 	/*
88015dc847eSJeff Roberson 	 * Claim that we've been running for one second for statistical
88115dc847eSJeff Roberson 	 * purposes.
88215dc847eSJeff Roberson 	 */
88315dc847eSJeff Roberson 	child->ke_ticks = 0;
88415dc847eSJeff Roberson 	child->ke_ltick = ticks;
88515dc847eSJeff Roberson 	child->ke_ftick = ticks - hz;
88615dc847eSJeff Roberson }
88715dc847eSJeff Roberson 
88815dc847eSJeff Roberson void
88915dc847eSJeff Roberson sched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child)
89015dc847eSJeff Roberson {
8912056d0a1SJohn Baldwin 
8922056d0a1SJohn Baldwin 	PROC_LOCK_ASSERT(child->kg_proc, MA_OWNED);
89335e6168fSJeff Roberson 	/* XXX Need something better here */
894210491d3SJeff Roberson 
895210491d3SJeff Roberson 	child->kg_slptime = kg->kg_slptime;
896210491d3SJeff Roberson 	child->kg_runtime = kg->kg_runtime;
8974b60e324SJeff Roberson 	kg->kg_runtime += tickincr << 10;
8984b60e324SJeff Roberson 	sched_interact_update(kg);
89915dc847eSJeff Roberson 
90035e6168fSJeff Roberson 	child->kg_user_pri = kg->kg_user_pri;
90115dc847eSJeff Roberson 	child->kg_nice = kg->kg_nice;
902c9f25d8fSJeff Roberson }
903c9f25d8fSJeff Roberson 
90415dc847eSJeff Roberson void
90515dc847eSJeff Roberson sched_fork_thread(struct thread *td, struct thread *child)
90615dc847eSJeff Roberson {
90715dc847eSJeff Roberson }
90815dc847eSJeff Roberson 
90915dc847eSJeff Roberson void
91015dc847eSJeff Roberson sched_class(struct ksegrp *kg, int class)
91115dc847eSJeff Roberson {
91215dc847eSJeff Roberson 	struct kseq *kseq;
91315dc847eSJeff Roberson 	struct kse *ke;
91415dc847eSJeff Roberson 
9152056d0a1SJohn Baldwin 	mtx_assert(&sched_lock, MA_OWNED);
91615dc847eSJeff Roberson 	if (kg->kg_pri_class == class)
91715dc847eSJeff Roberson 		return;
91815dc847eSJeff Roberson 
91915dc847eSJeff Roberson 	FOREACH_KSE_IN_GROUP(kg, ke) {
92015dc847eSJeff Roberson 		if (ke->ke_state != KES_ONRUNQ &&
92115dc847eSJeff Roberson 		    ke->ke_state != KES_THREAD)
92215dc847eSJeff Roberson 			continue;
92315dc847eSJeff Roberson 		kseq = KSEQ_CPU(ke->ke_cpu);
92415dc847eSJeff Roberson 
925b5c4c4a7SJeff Roberson 		kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--;
926b5c4c4a7SJeff Roberson 		kseq->ksq_loads[PRI_BASE(class)]++;
92715dc847eSJeff Roberson 
92815dc847eSJeff Roberson 		if (kg->kg_pri_class == PRI_TIMESHARE)
92915dc847eSJeff Roberson 			kseq_nice_rem(kseq, kg->kg_nice);
93015dc847eSJeff Roberson 		else if (class == PRI_TIMESHARE)
93115dc847eSJeff Roberson 			kseq_nice_add(kseq, kg->kg_nice);
93215dc847eSJeff Roberson 	}
93315dc847eSJeff Roberson 
93415dc847eSJeff Roberson 	kg->kg_pri_class = class;
93535e6168fSJeff Roberson }
93635e6168fSJeff Roberson 
93735e6168fSJeff Roberson /*
93835e6168fSJeff Roberson  * Return some of the child's priority and interactivity to the parent.
93935e6168fSJeff Roberson  */
94035e6168fSJeff Roberson void
94115dc847eSJeff Roberson sched_exit(struct proc *p, struct proc *child)
94235e6168fSJeff Roberson {
94335e6168fSJeff Roberson 	/* XXX Need something better here */
94435e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
945141ad61cSJeff Roberson 	sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child));
946210491d3SJeff Roberson 	sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(child));
947141ad61cSJeff Roberson }
948141ad61cSJeff Roberson 
949141ad61cSJeff Roberson void
950141ad61cSJeff Roberson sched_exit_kse(struct kse *ke, struct kse *child)
951141ad61cSJeff Roberson {
952141ad61cSJeff Roberson 	kseq_rem(KSEQ_CPU(child->ke_cpu), child);
953141ad61cSJeff Roberson }
954141ad61cSJeff Roberson 
955141ad61cSJeff Roberson void
956141ad61cSJeff Roberson sched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child)
957141ad61cSJeff Roberson {
9584b60e324SJeff Roberson 	/* kg->kg_slptime += child->kg_slptime; */
959210491d3SJeff Roberson 	kg->kg_runtime += child->kg_runtime;
9604b60e324SJeff Roberson 	sched_interact_update(kg);
961141ad61cSJeff Roberson }
962141ad61cSJeff Roberson 
963141ad61cSJeff Roberson void
964141ad61cSJeff Roberson sched_exit_thread(struct thread *td, struct thread *child)
965141ad61cSJeff Roberson {
96635e6168fSJeff Roberson }
96735e6168fSJeff Roberson 
96835e6168fSJeff Roberson void
96915dc847eSJeff Roberson sched_clock(struct kse *ke)
97035e6168fSJeff Roberson {
97135e6168fSJeff Roberson 	struct kseq *kseq;
9720a016a05SJeff Roberson 	struct ksegrp *kg;
97315dc847eSJeff Roberson 	struct thread *td;
97415dc847eSJeff Roberson #if 0
97515dc847eSJeff Roberson 	struct kse *nke;
97615dc847eSJeff Roberson #endif
97735e6168fSJeff Roberson 
97815dc847eSJeff Roberson 	/*
97915dc847eSJeff Roberson 	 * sched_setup() apparently happens prior to stathz being set.  We
98015dc847eSJeff Roberson 	 * need to resolve the timers earlier in the boot so we can avoid
98115dc847eSJeff Roberson 	 * calculating this here.
98215dc847eSJeff Roberson 	 */
98315dc847eSJeff Roberson 	if (realstathz == 0) {
98415dc847eSJeff Roberson 		realstathz = stathz ? stathz : hz;
98515dc847eSJeff Roberson 		tickincr = hz / realstathz;
98615dc847eSJeff Roberson 		/*
98715dc847eSJeff Roberson 		 * XXX This does not work for values of stathz that are much
98815dc847eSJeff Roberson 		 * larger than hz.
98915dc847eSJeff Roberson 		 */
99015dc847eSJeff Roberson 		if (tickincr == 0)
99115dc847eSJeff Roberson 			tickincr = 1;
99215dc847eSJeff Roberson 	}
99335e6168fSJeff Roberson 
99415dc847eSJeff Roberson 	td = ke->ke_thread;
99515dc847eSJeff Roberson 	kg = ke->ke_ksegrp;
99635e6168fSJeff Roberson 
9970a016a05SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
9980a016a05SJeff Roberson 	KASSERT((td != NULL), ("schedclock: null thread pointer"));
9990a016a05SJeff Roberson 
10000a016a05SJeff Roberson 	/* Adjust ticks for pctcpu */
100165c8760dSJeff Roberson 	ke->ke_ticks++;
1002d465fb95SJeff Roberson 	ke->ke_ltick = ticks;
1003a8949de2SJeff Roberson 
1004d465fb95SJeff Roberson 	/* Go up to one second beyond our max and then trim back down */
1005d465fb95SJeff Roberson 	if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick)
1006d465fb95SJeff Roberson 		sched_pctcpu_update(ke);
1007d465fb95SJeff Roberson 
100843fdafb1SJulian Elischer 	if (td->td_flags & TDF_IDLETD)
100935e6168fSJeff Roberson 		return;
10100a016a05SJeff Roberson 
101115dc847eSJeff Roberson 	CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)",
101215dc847eSJeff Roberson 	    ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10);
1013c9f25d8fSJeff Roberson 
101435e6168fSJeff Roberson 	/*
1015a8949de2SJeff Roberson 	 * We only do slicing code for TIMESHARE ksegrps.
1016a8949de2SJeff Roberson 	 */
1017a8949de2SJeff Roberson 	if (kg->kg_pri_class != PRI_TIMESHARE)
1018a8949de2SJeff Roberson 		return;
1019a8949de2SJeff Roberson 	/*
102015dc847eSJeff Roberson 	 * Check for a higher priority task on the run queue.  This can happen
102115dc847eSJeff Roberson 	 * on SMP if another processor woke up a process on our runq.
102235e6168fSJeff Roberson 	 */
102315dc847eSJeff Roberson 	kseq = KSEQ_SELF();
102415dc847eSJeff Roberson #if 0
102515dc847eSJeff Roberson 	if (kseq->ksq_load > 1 && (nke = kseq_choose(kseq)) != NULL) {
102615dc847eSJeff Roberson 		if (sched_strict &&
102715dc847eSJeff Roberson 		    nke->ke_thread->td_priority < td->td_priority)
102815dc847eSJeff Roberson 			td->td_flags |= TDF_NEEDRESCHED;
102915dc847eSJeff Roberson 		else if (nke->ke_thread->td_priority <
103015dc847eSJeff Roberson 		    td->td_priority SCHED_PRIO_SLOP)
103115dc847eSJeff Roberson 
103215dc847eSJeff Roberson 		if (nke->ke_thread->td_priority < td->td_priority)
103315dc847eSJeff Roberson 			td->td_flags |= TDF_NEEDRESCHED;
103415dc847eSJeff Roberson 	}
103515dc847eSJeff Roberson #endif
103615dc847eSJeff Roberson 	/*
103715dc847eSJeff Roberson 	 * We used a tick charge it to the ksegrp so that we can compute our
103815dc847eSJeff Roberson 	 * interactivity.
103915dc847eSJeff Roberson 	 */
104015dc847eSJeff Roberson 	kg->kg_runtime += tickincr << 10;
10414b60e324SJeff Roberson 	sched_interact_update(kg);
1042407b0157SJeff Roberson 
104335e6168fSJeff Roberson 	/*
104435e6168fSJeff Roberson 	 * We used up one time slice.
104535e6168fSJeff Roberson 	 */
104635e6168fSJeff Roberson 	ke->ke_slice--;
104715dc847eSJeff Roberson #ifdef SMP
1048c36ccfa2SJeff Roberson 	kseq->ksq_rslices--;
104915dc847eSJeff Roberson #endif
105015dc847eSJeff Roberson 
105115dc847eSJeff Roberson 	if (ke->ke_slice > 0)
105215dc847eSJeff Roberson 		return;
105335e6168fSJeff Roberson 	/*
105415dc847eSJeff Roberson 	 * We're out of time, recompute priorities and requeue.
105535e6168fSJeff Roberson 	 */
105615dc847eSJeff Roberson 	kseq_rem(kseq, ke);
1057e1f89c22SJeff Roberson 	sched_priority(kg);
105815dc847eSJeff Roberson 	sched_slice(ke);
105915dc847eSJeff Roberson 	if (SCHED_CURR(kg, ke))
106015dc847eSJeff Roberson 		ke->ke_runq = kseq->ksq_curr;
106115dc847eSJeff Roberson 	else
106215dc847eSJeff Roberson 		ke->ke_runq = kseq->ksq_next;
106315dc847eSJeff Roberson 	kseq_add(kseq, ke);
10644a338afdSJulian Elischer 	td->td_flags |= TDF_NEEDRESCHED;
106535e6168fSJeff Roberson }
106635e6168fSJeff Roberson 
106735e6168fSJeff Roberson int
106835e6168fSJeff Roberson sched_runnable(void)
106935e6168fSJeff Roberson {
107035e6168fSJeff Roberson 	struct kseq *kseq;
1071b90816f1SJeff Roberson 	int load;
107235e6168fSJeff Roberson 
1073b90816f1SJeff Roberson 	load = 1;
1074b90816f1SJeff Roberson 
1075b90816f1SJeff Roberson 	mtx_lock_spin(&sched_lock);
10760a016a05SJeff Roberson 	kseq = KSEQ_SELF();
107735e6168fSJeff Roberson 
107815dc847eSJeff Roberson 	if (kseq->ksq_load)
1079b90816f1SJeff Roberson 		goto out;
1080c9f25d8fSJeff Roberson #ifdef SMP
10810a016a05SJeff Roberson 	/*
10820a016a05SJeff Roberson 	 * For SMP we may steal other processor's KSEs.  Just search until we
10830a016a05SJeff Roberson 	 * verify that at least on other cpu has a runnable task.
10840a016a05SJeff Roberson 	 */
1085c9f25d8fSJeff Roberson 	if (smp_started) {
1086c9f25d8fSJeff Roberson 		int i;
1087c9f25d8fSJeff Roberson 
1088c9f25d8fSJeff Roberson 		for (i = 0; i < mp_maxid; i++) {
1089c9f25d8fSJeff Roberson 			if (CPU_ABSENT(i))
1090c9f25d8fSJeff Roberson 				continue;
10910a016a05SJeff Roberson 			kseq = KSEQ_CPU(i);
10927cd650a9SJeff Roberson 			if (kseq->ksq_load > 1)
1093b90816f1SJeff Roberson 				goto out;
1094c9f25d8fSJeff Roberson 		}
1095c9f25d8fSJeff Roberson 	}
1096c9f25d8fSJeff Roberson #endif
1097b90816f1SJeff Roberson 	load = 0;
1098b90816f1SJeff Roberson out:
1099b90816f1SJeff Roberson 	mtx_unlock_spin(&sched_lock);
1100b90816f1SJeff Roberson 	return (load);
110135e6168fSJeff Roberson }
110235e6168fSJeff Roberson 
110335e6168fSJeff Roberson void
110435e6168fSJeff Roberson sched_userret(struct thread *td)
110535e6168fSJeff Roberson {
110635e6168fSJeff Roberson 	struct ksegrp *kg;
1107210491d3SJeff Roberson 	struct kseq *kseq;
1108210491d3SJeff Roberson 	struct kse *ke;
110935e6168fSJeff Roberson 
111035e6168fSJeff Roberson 	kg = td->td_ksegrp;
111135e6168fSJeff Roberson 
111235e6168fSJeff Roberson 	if (td->td_priority != kg->kg_user_pri) {
111335e6168fSJeff Roberson 		mtx_lock_spin(&sched_lock);
111435e6168fSJeff Roberson 		td->td_priority = kg->kg_user_pri;
1115210491d3SJeff Roberson 		kseq = KSEQ_SELF();
1116210491d3SJeff Roberson 		if (td->td_ksegrp->kg_pri_class == PRI_TIMESHARE &&
1117210491d3SJeff Roberson 		    kseq->ksq_load > 1 &&
1118210491d3SJeff Roberson 		    (ke = kseq_choose(kseq)) != NULL &&
1119210491d3SJeff Roberson 		    ke->ke_thread->td_priority < td->td_priority)
1120210491d3SJeff Roberson 			curthread->td_flags |= TDF_NEEDRESCHED;
112135e6168fSJeff Roberson 		mtx_unlock_spin(&sched_lock);
112235e6168fSJeff Roberson 	}
112335e6168fSJeff Roberson }
112435e6168fSJeff Roberson 
1125c9f25d8fSJeff Roberson struct kse *
1126c9f25d8fSJeff Roberson sched_choose(void)
1127c9f25d8fSJeff Roberson {
11280a016a05SJeff Roberson 	struct kseq *kseq;
1129c9f25d8fSJeff Roberson 	struct kse *ke;
113015dc847eSJeff Roberson 
1131b90816f1SJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
113215dc847eSJeff Roberson #ifdef SMP
1133245f3abfSJeff Roberson retry:
113415dc847eSJeff Roberson #endif
1135c36ccfa2SJeff Roberson 	kseq = KSEQ_SELF();
11360a016a05SJeff Roberson 	ke = kseq_choose(kseq);
113735e6168fSJeff Roberson 	if (ke) {
113815dc847eSJeff Roberson 		runq_remove(ke->ke_runq, ke);
113935e6168fSJeff Roberson 		ke->ke_state = KES_THREAD;
1140245f3abfSJeff Roberson 
114115dc847eSJeff Roberson 		if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) {
114215dc847eSJeff Roberson 			CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)",
114315dc847eSJeff Roberson 			    ke, ke->ke_runq, ke->ke_slice,
114415dc847eSJeff Roberson 			    ke->ke_thread->td_priority);
1145245f3abfSJeff Roberson 		}
114615dc847eSJeff Roberson 		return (ke);
114735e6168fSJeff Roberson 	}
114835e6168fSJeff Roberson 
1149c9f25d8fSJeff Roberson #ifdef SMP
1150c36ccfa2SJeff Roberson 	if (smp_started) {
1151c9f25d8fSJeff Roberson 		/*
1152c9f25d8fSJeff Roberson 		 * Find the cpu with the highest load and steal one proc.
1153c9f25d8fSJeff Roberson 		 */
1154c36ccfa2SJeff Roberson 		if ((kseq = kseq_load_highest()) == NULL)
1155c36ccfa2SJeff Roberson 			return (NULL);
1156c36ccfa2SJeff Roberson 
1157c36ccfa2SJeff Roberson 		/*
1158c36ccfa2SJeff Roberson 		 * Remove this kse from this kseq and runq and then requeue
1159c36ccfa2SJeff Roberson 		 * on the current processor.  Then we will dequeue it
1160c36ccfa2SJeff Roberson 		 * normally above.
1161c36ccfa2SJeff Roberson 		 */
1162356500a3SJeff Roberson 		kseq_move(kseq, PCPU_GET(cpuid));
116315dc847eSJeff Roberson 		goto retry;
1164c9f25d8fSJeff Roberson 	}
1165c9f25d8fSJeff Roberson #endif
116615dc847eSJeff Roberson 
116715dc847eSJeff Roberson 	return (NULL);
116835e6168fSJeff Roberson }
116935e6168fSJeff Roberson 
117035e6168fSJeff Roberson void
117135e6168fSJeff Roberson sched_add(struct kse *ke)
117235e6168fSJeff Roberson {
1173c9f25d8fSJeff Roberson 	struct kseq *kseq;
117415dc847eSJeff Roberson 	struct ksegrp *kg;
1175c9f25d8fSJeff Roberson 
11765d7ef00cSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
11775d7ef00cSJeff Roberson 	KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE"));
11785d7ef00cSJeff Roberson 	KASSERT((ke->ke_thread->td_kse != NULL),
11795d7ef00cSJeff Roberson 	    ("sched_add: No KSE on thread"));
11805d7ef00cSJeff Roberson 	KASSERT(ke->ke_state != KES_ONRUNQ,
11815d7ef00cSJeff Roberson 	    ("sched_add: kse %p (%s) already in run queue", ke,
11825d7ef00cSJeff Roberson 	    ke->ke_proc->p_comm));
11835d7ef00cSJeff Roberson 	KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
11845d7ef00cSJeff Roberson 	    ("sched_add: process swapped out"));
11859bca28a7SJeff Roberson 	KASSERT(ke->ke_runq == NULL,
11869bca28a7SJeff Roberson 	    ("sched_add: KSE %p is still assigned to a run queue", ke));
11875d7ef00cSJeff Roberson 
118815dc847eSJeff Roberson 	kg = ke->ke_ksegrp;
118915dc847eSJeff Roberson 
1190b5c4c4a7SJeff Roberson 	switch (PRI_BASE(kg->kg_pri_class)) {
1191a8949de2SJeff Roberson 	case PRI_ITHD:
1192a8949de2SJeff Roberson 	case PRI_REALTIME:
1193a6ed4186SJeff Roberson 		kseq = KSEQ_SELF();
119415dc847eSJeff Roberson 		ke->ke_runq = kseq->ksq_curr;
119515dc847eSJeff Roberson 		ke->ke_slice = SCHED_SLICE_MAX;
11967cd650a9SJeff Roberson 		ke->ke_cpu = PCPU_GET(cpuid);
1197a8949de2SJeff Roberson 		break;
1198a8949de2SJeff Roberson 	case PRI_TIMESHARE:
1199a8949de2SJeff Roberson 		kseq = KSEQ_CPU(ke->ke_cpu);
120015dc847eSJeff Roberson 		if (SCHED_CURR(kg, ke))
120115dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_curr;
120215dc847eSJeff Roberson 		else
120315dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_next;
120415dc847eSJeff Roberson 		break;
120515dc847eSJeff Roberson 	case PRI_IDLE:
120615dc847eSJeff Roberson 		kseq = KSEQ_CPU(ke->ke_cpu);
120715dc847eSJeff Roberson 		/*
120815dc847eSJeff Roberson 		 * This is for priority prop.
120915dc847eSJeff Roberson 		 */
1210210491d3SJeff Roberson 		if (ke->ke_thread->td_priority > PRI_MIN_IDLE)
121115dc847eSJeff Roberson 			ke->ke_runq = kseq->ksq_curr;
121215dc847eSJeff Roberson 		else
121315dc847eSJeff Roberson 			ke->ke_runq = &kseq->ksq_idle;
121415dc847eSJeff Roberson 		ke->ke_slice = SCHED_SLICE_MIN;
121515dc847eSJeff Roberson 		break;
121615dc847eSJeff Roberson 	default:
121715dc847eSJeff Roberson 		panic("Unknown pri class.\n");
1218a8949de2SJeff Roberson 		break;
1219a6ed4186SJeff Roberson 	}
1220a8949de2SJeff Roberson 
122135e6168fSJeff Roberson 	ke->ke_ksegrp->kg_runq_kses++;
122235e6168fSJeff Roberson 	ke->ke_state = KES_ONRUNQ;
122335e6168fSJeff Roberson 
122415dc847eSJeff Roberson 	runq_add(ke->ke_runq, ke);
12259bca28a7SJeff Roberson 	kseq_add(kseq, ke);
122635e6168fSJeff Roberson }
122735e6168fSJeff Roberson 
122835e6168fSJeff Roberson void
122935e6168fSJeff Roberson sched_rem(struct kse *ke)
123035e6168fSJeff Roberson {
123115dc847eSJeff Roberson 	struct kseq *kseq;
123215dc847eSJeff Roberson 
123335e6168fSJeff Roberson 	mtx_assert(&sched_lock, MA_OWNED);
12349bca28a7SJeff Roberson 	KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue"));
123535e6168fSJeff Roberson 
123635e6168fSJeff Roberson 	ke->ke_state = KES_THREAD;
123735e6168fSJeff Roberson 	ke->ke_ksegrp->kg_runq_kses--;
123815dc847eSJeff Roberson 	kseq = KSEQ_CPU(ke->ke_cpu);
123915dc847eSJeff Roberson 	runq_remove(ke->ke_runq, ke);
124015dc847eSJeff Roberson 	kseq_rem(kseq, ke);
124135e6168fSJeff Roberson }
124235e6168fSJeff Roberson 
124335e6168fSJeff Roberson fixpt_t
124435e6168fSJeff Roberson sched_pctcpu(struct kse *ke)
124535e6168fSJeff Roberson {
124635e6168fSJeff Roberson 	fixpt_t pctcpu;
124735e6168fSJeff Roberson 
124835e6168fSJeff Roberson 	pctcpu = 0;
124935e6168fSJeff Roberson 
1250b90816f1SJeff Roberson 	mtx_lock_spin(&sched_lock);
125135e6168fSJeff Roberson 	if (ke->ke_ticks) {
125235e6168fSJeff Roberson 		int rtick;
125335e6168fSJeff Roberson 
125435e6168fSJeff Roberson 		/* Update to account for time potentially spent sleeping */
125535e6168fSJeff Roberson 		ke->ke_ltick = ticks;
1256210491d3SJeff Roberson 		/*
1257210491d3SJeff Roberson 		 * Don't update more frequently than twice a second.  Allowing
1258210491d3SJeff Roberson 		 * this causes the cpu usage to decay away too quickly due to
1259210491d3SJeff Roberson 		 * rounding errors.
1260210491d3SJeff Roberson 		 */
1261210491d3SJeff Roberson 		if (ke->ke_ltick < (ticks - (hz / 2)))
126235e6168fSJeff Roberson 			sched_pctcpu_update(ke);
126335e6168fSJeff Roberson 
126435e6168fSJeff Roberson 		/* How many rtick per second ? */
1265210491d3SJeff Roberson 		rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS);
12667121cce5SScott Long 		pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT;
126735e6168fSJeff Roberson 	}
126835e6168fSJeff Roberson 
126935e6168fSJeff Roberson 	ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick;
1270828e7683SJohn Baldwin 	mtx_unlock_spin(&sched_lock);
127135e6168fSJeff Roberson 
127235e6168fSJeff Roberson 	return (pctcpu);
127335e6168fSJeff Roberson }
127435e6168fSJeff Roberson 
127535e6168fSJeff Roberson int
127635e6168fSJeff Roberson sched_sizeof_kse(void)
127735e6168fSJeff Roberson {
127835e6168fSJeff Roberson 	return (sizeof(struct kse) + sizeof(struct ke_sched));
127935e6168fSJeff Roberson }
128035e6168fSJeff Roberson 
128135e6168fSJeff Roberson int
128235e6168fSJeff Roberson sched_sizeof_ksegrp(void)
128335e6168fSJeff Roberson {
128435e6168fSJeff Roberson 	return (sizeof(struct ksegrp) + sizeof(struct kg_sched));
128535e6168fSJeff Roberson }
128635e6168fSJeff Roberson 
128735e6168fSJeff Roberson int
128835e6168fSJeff Roberson sched_sizeof_proc(void)
128935e6168fSJeff Roberson {
129035e6168fSJeff Roberson 	return (sizeof(struct proc));
129135e6168fSJeff Roberson }
129235e6168fSJeff Roberson 
129335e6168fSJeff Roberson int
129435e6168fSJeff Roberson sched_sizeof_thread(void)
129535e6168fSJeff Roberson {
129635e6168fSJeff Roberson 	return (sizeof(struct thread) + sizeof(struct td_sched));
129735e6168fSJeff Roberson }
1298