sched_ule.c revision 116377
1/*-
2 * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice unmodified, this list of conditions, and the following
10 *    disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <sys/cdefs.h>
28__FBSDID("$FreeBSD: head/sys/kern/sched_ule.c 116377 2003-06-15 04:14:25Z jeff $");
29
30#include <sys/param.h>
31#include <sys/systm.h>
32#include <sys/kernel.h>
33#include <sys/ktr.h>
34#include <sys/lock.h>
35#include <sys/mutex.h>
36#include <sys/proc.h>
37#include <sys/resource.h>
38#include <sys/sched.h>
39#include <sys/smp.h>
40#include <sys/sx.h>
41#include <sys/sysctl.h>
42#include <sys/sysproto.h>
43#include <sys/vmmeter.h>
44#ifdef DDB
45#include <ddb/ddb.h>
46#endif
47#ifdef KTRACE
48#include <sys/uio.h>
49#include <sys/ktrace.h>
50#endif
51
52#include <machine/cpu.h>
53
54#define KTR_ULE         KTR_NFS
55
56/* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
57/* XXX This is bogus compatability crap for ps */
58static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
59SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
60
61static void sched_setup(void *dummy);
62SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
63
64static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED");
65
66static int sched_strict;
67SYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, "");
68
69static int slice_min = 1;
70SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, "");
71
72static int slice_max = 10;
73SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, "");
74
75int realstathz;
76int tickincr = 1;
77
78#ifdef SMP
79/* Callout to handle load balancing SMP systems. */
80static struct callout kseq_lb_callout;
81#endif
82
83/*
84 * These datastructures are allocated within their parent datastructure but
85 * are scheduler specific.
86 */
87
88struct ke_sched {
89	int		ske_slice;
90	struct runq	*ske_runq;
91	/* The following variables are only used for pctcpu calculation */
92	int		ske_ltick;	/* Last tick that we were running on */
93	int		ske_ftick;	/* First tick that we were running on */
94	int		ske_ticks;	/* Tick count */
95	/* CPU that we have affinity for. */
96	u_char		ske_cpu;
97};
98#define	ke_slice	ke_sched->ske_slice
99#define	ke_runq		ke_sched->ske_runq
100#define	ke_ltick	ke_sched->ske_ltick
101#define	ke_ftick	ke_sched->ske_ftick
102#define	ke_ticks	ke_sched->ske_ticks
103#define	ke_cpu		ke_sched->ske_cpu
104
105struct kg_sched {
106	int	skg_slptime;		/* Number of ticks we vol. slept */
107	int	skg_runtime;		/* Number of ticks we were running */
108};
109#define	kg_slptime	kg_sched->skg_slptime
110#define	kg_runtime	kg_sched->skg_runtime
111
112struct td_sched {
113	int	std_slptime;
114};
115#define	td_slptime	td_sched->std_slptime
116
117struct td_sched td_sched;
118struct ke_sched ke_sched;
119struct kg_sched kg_sched;
120
121struct ke_sched *kse0_sched = &ke_sched;
122struct kg_sched *ksegrp0_sched = &kg_sched;
123struct p_sched *proc0_sched = NULL;
124struct td_sched *thread0_sched = &td_sched;
125
126/*
127 * This priority range has 20 priorities on either end that are reachable
128 * only through nice values.
129 *
130 * PRI_RANGE:	Total priority range for timeshare threads.
131 * PRI_NRESV:	Reserved priorities for nice.
132 * PRI_BASE:	The start of the dynamic range.
133 * DYN_RANGE:	Number of priorities that are available int the dynamic
134 *		priority range.
135 */
136#define	SCHED_PRI_RANGE		(PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
137#define	SCHED_PRI_NRESV		PRIO_TOTAL
138#define	SCHED_PRI_NHALF		(PRIO_TOTAL / 2)
139#define	SCHED_PRI_NTHRESH	(SCHED_PRI_NHALF - 1)
140#define	SCHED_PRI_BASE		((SCHED_PRI_NRESV / 2) + PRI_MIN_TIMESHARE)
141#define	SCHED_DYN_RANGE		(SCHED_PRI_RANGE - SCHED_PRI_NRESV)
142#define	SCHED_PRI_INTERACT(score)					\
143    ((score) * SCHED_DYN_RANGE / SCHED_INTERACT_MAX)
144
145/*
146 * These determine the interactivity of a process.
147 *
148 * SLP_RUN_MAX:	Maximum amount of sleep time + run time we'll accumulate
149 *		before throttling back.
150 * SLP_RUN_THROTTLE:	Divisor for reducing slp/run time.
151 * INTERACT_MAX:	Maximum interactivity value.  Smaller is better.
152 * INTERACT_THRESH:	Threshhold for placement on the current runq.
153 */
154#define	SCHED_SLP_RUN_MAX	((hz / 4) << 10)
155#define	SCHED_SLP_RUN_THROTTLE	(2)
156#define	SCHED_INTERACT_MAX	(100)
157#define	SCHED_INTERACT_HALF	(SCHED_INTERACT_MAX / 2)
158#define	SCHED_INTERACT_THRESH	(20)
159
160/*
161 * These parameters and macros determine the size of the time slice that is
162 * granted to each thread.
163 *
164 * SLICE_MIN:	Minimum time slice granted, in units of ticks.
165 * SLICE_MAX:	Maximum time slice granted.
166 * SLICE_RANGE:	Range of available time slices scaled by hz.
167 * SLICE_SCALE:	The number slices granted per val in the range of [0, max].
168 * SLICE_NICE:  Determine the amount of slice granted to a scaled nice.
169 */
170#define	SCHED_SLICE_MIN			(slice_min)
171#define	SCHED_SLICE_MAX			(slice_max)
172#define	SCHED_SLICE_RANGE		(SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1)
173#define	SCHED_SLICE_SCALE(val, max)	(((val) * SCHED_SLICE_RANGE) / (max))
174#define	SCHED_SLICE_NICE(nice)						\
175    (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_PRI_NTHRESH))
176
177/*
178 * This macro determines whether or not the kse belongs on the current or
179 * next run queue.
180 *
181 * XXX nice value should effect how interactive a kg is.
182 */
183#define	SCHED_INTERACTIVE(kg)						\
184    (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
185#define	SCHED_CURR(kg, ke)						\
186    (ke->ke_thread->td_priority < PRI_MIN_TIMESHARE || SCHED_INTERACTIVE(kg))
187
188/*
189 * Cpu percentage computation macros and defines.
190 *
191 * SCHED_CPU_TIME:	Number of seconds to average the cpu usage across.
192 * SCHED_CPU_TICKS:	Number of hz ticks to average the cpu usage across.
193 */
194
195#define	SCHED_CPU_TIME	10
196#define	SCHED_CPU_TICKS	(hz * SCHED_CPU_TIME)
197
198/*
199 * kseq - per processor runqs and statistics.
200 */
201
202#define	KSEQ_NCLASS	(PRI_IDLE + 1)	/* Number of run classes. */
203
204struct kseq {
205	struct runq	ksq_idle;		/* Queue of IDLE threads. */
206	struct runq	ksq_timeshare[2];	/* Run queues for !IDLE. */
207	struct runq	*ksq_next;		/* Next timeshare queue. */
208	struct runq	*ksq_curr;		/* Current queue. */
209	int		ksq_loads[KSEQ_NCLASS];	/* Load for each class */
210	int		ksq_load;		/* Aggregate load. */
211	short		ksq_nice[PRIO_TOTAL + 1]; /* KSEs in each nice bin. */
212	short		ksq_nicemin;		/* Least nice. */
213#ifdef SMP
214	unsigned int	ksq_rslices;	/* Slices on run queue */
215#endif
216};
217
218/*
219 * One kse queue per processor.
220 */
221#ifdef SMP
222struct kseq	kseq_cpu[MAXCPU];
223#define	KSEQ_SELF()	(&kseq_cpu[PCPU_GET(cpuid)])
224#define	KSEQ_CPU(x)	(&kseq_cpu[(x)])
225#else
226struct kseq	kseq_cpu;
227#define	KSEQ_SELF()	(&kseq_cpu)
228#define	KSEQ_CPU(x)	(&kseq_cpu)
229#endif
230
231static void sched_slice(struct kse *ke);
232static void sched_priority(struct ksegrp *kg);
233static int sched_interact_score(struct ksegrp *kg);
234void sched_pctcpu_update(struct kse *ke);
235int sched_pickcpu(void);
236
237/* Operations on per processor queues */
238static struct kse * kseq_choose(struct kseq *kseq);
239static void kseq_setup(struct kseq *kseq);
240static void kseq_add(struct kseq *kseq, struct kse *ke);
241static void kseq_rem(struct kseq *kseq, struct kse *ke);
242static void kseq_nice_add(struct kseq *kseq, int nice);
243static void kseq_nice_rem(struct kseq *kseq, int nice);
244void kseq_print(int cpu);
245#ifdef SMP
246struct kseq * kseq_load_highest(void);
247void kseq_balance(void *arg);
248void kseq_move(struct kseq *from, int cpu);
249#endif
250
251void
252kseq_print(int cpu)
253{
254	struct kseq *kseq;
255	int i;
256
257	kseq = KSEQ_CPU(cpu);
258
259	printf("kseq:\n");
260	printf("\tload:           %d\n", kseq->ksq_load);
261	printf("\tload ITHD:      %d\n", kseq->ksq_loads[PRI_ITHD]);
262	printf("\tload REALTIME:  %d\n", kseq->ksq_loads[PRI_REALTIME]);
263	printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]);
264	printf("\tload IDLE:      %d\n", kseq->ksq_loads[PRI_IDLE]);
265	printf("\tnicemin:\t%d\n", kseq->ksq_nicemin);
266	printf("\tnice counts:\n");
267	for (i = 0; i < PRIO_TOTAL + 1; i++)
268		if (kseq->ksq_nice[i])
269			printf("\t\t%d = %d\n",
270			    i - SCHED_PRI_NHALF, kseq->ksq_nice[i]);
271}
272
273static void
274kseq_add(struct kseq *kseq, struct kse *ke)
275{
276	mtx_assert(&sched_lock, MA_OWNED);
277	kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++;
278	kseq->ksq_load++;
279	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
280	CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))",
281	    ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority,
282	    ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin);
283	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
284		kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice);
285#ifdef SMP
286	kseq->ksq_rslices += ke->ke_slice;
287#endif
288}
289
290static void
291kseq_rem(struct kseq *kseq, struct kse *ke)
292{
293	mtx_assert(&sched_lock, MA_OWNED);
294	kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--;
295	kseq->ksq_load--;
296	ke->ke_runq = NULL;
297	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
298		kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice);
299#ifdef SMP
300	kseq->ksq_rslices -= ke->ke_slice;
301#endif
302}
303
304static void
305kseq_nice_add(struct kseq *kseq, int nice)
306{
307	mtx_assert(&sched_lock, MA_OWNED);
308	/* Normalize to zero. */
309	kseq->ksq_nice[nice + SCHED_PRI_NHALF]++;
310	if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 1)
311		kseq->ksq_nicemin = nice;
312}
313
314static void
315kseq_nice_rem(struct kseq *kseq, int nice)
316{
317	int n;
318
319	mtx_assert(&sched_lock, MA_OWNED);
320	/* Normalize to zero. */
321	n = nice + SCHED_PRI_NHALF;
322	kseq->ksq_nice[n]--;
323	KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count."));
324
325	/*
326	 * If this wasn't the smallest nice value or there are more in
327	 * this bucket we can just return.  Otherwise we have to recalculate
328	 * the smallest nice.
329	 */
330	if (nice != kseq->ksq_nicemin ||
331	    kseq->ksq_nice[n] != 0 ||
332	    kseq->ksq_loads[PRI_TIMESHARE] == 0)
333		return;
334
335	for (; n < SCHED_PRI_NRESV + 1; n++)
336		if (kseq->ksq_nice[n]) {
337			kseq->ksq_nicemin = n - SCHED_PRI_NHALF;
338			return;
339		}
340}
341
342#ifdef SMP
343/*
344 * kseq_balance is a simple CPU load balancing algorithm.  It operates by
345 * finding the least loaded and most loaded cpu and equalizing their load
346 * by migrating some processes.
347 *
348 * Dealing only with two CPUs at a time has two advantages.  Firstly, most
349 * installations will only have 2 cpus.  Secondly, load balancing too much at
350 * once can have an unpleasant effect on the system.  The scheduler rarely has
351 * enough information to make perfect decisions.  So this algorithm chooses
352 * algorithm simplicity and more gradual effects on load in larger systems.
353 *
354 * It could be improved by considering the priorities and slices assigned to
355 * each task prior to balancing them.  There are many pathological cases with
356 * any approach and so the semi random algorithm below may work as well as any.
357 *
358 */
359void
360kseq_balance(void *arg)
361{
362	struct kseq *kseq;
363	int high_load;
364	int low_load;
365	int high_cpu;
366	int low_cpu;
367	int move;
368	int diff;
369	int i;
370
371	high_cpu = 0;
372	low_cpu = 0;
373	high_load = 0;
374	low_load = -1;
375
376	mtx_lock_spin(&sched_lock);
377	for (i = 0; i < mp_maxid; i++) {
378		if (CPU_ABSENT(i))
379			continue;
380		kseq = KSEQ_CPU(i);
381		if (kseq->ksq_load > high_load) {
382			high_load = kseq->ksq_load;
383			high_cpu = i;
384		}
385		if (low_load == -1 || kseq->ksq_load < low_load) {
386			low_load = kseq->ksq_load;
387			low_cpu = i;
388		}
389	}
390
391	/*
392	 * Nothing to do.
393	 */
394	if (high_load < 2 || low_load == high_load)
395		goto out;
396
397	diff = high_load - low_load;
398	move = diff / 2;
399	if (diff & 0x1)
400		move++;
401
402	for (i = 0; i < move; i++)
403		kseq_move(KSEQ_CPU(high_cpu), low_cpu);
404
405out:
406	mtx_unlock_spin(&sched_lock);
407	callout_reset(&kseq_lb_callout, hz, kseq_balance, NULL);
408
409	return;
410}
411
412struct kseq *
413kseq_load_highest(void)
414{
415	struct kseq *kseq;
416	int load;
417	int cpu;
418	int i;
419
420	mtx_assert(&sched_lock, MA_OWNED);
421	cpu = 0;
422	load = 0;
423
424	for (i = 0; i < mp_maxid; i++) {
425		if (CPU_ABSENT(i))
426			continue;
427		kseq = KSEQ_CPU(i);
428		if (kseq->ksq_load > load) {
429			load = kseq->ksq_load;
430			cpu = i;
431		}
432	}
433	if (load > 1)
434		return (KSEQ_CPU(cpu));
435
436	return (NULL);
437}
438
439void
440kseq_move(struct kseq *from, int cpu)
441{
442	struct kse *ke;
443
444	ke = kseq_choose(from);
445	runq_remove(ke->ke_runq, ke);
446	ke->ke_state = KES_THREAD;
447	kseq_rem(from, ke);
448
449	ke->ke_cpu = cpu;
450	sched_add(ke);
451}
452#endif
453
454struct kse *
455kseq_choose(struct kseq *kseq)
456{
457	struct kse *ke;
458	struct runq *swap;
459
460	mtx_assert(&sched_lock, MA_OWNED);
461	swap = NULL;
462
463	for (;;) {
464		ke = runq_choose(kseq->ksq_curr);
465		if (ke == NULL) {
466			/*
467			 * We already swaped once and didn't get anywhere.
468			 */
469			if (swap)
470				break;
471			swap = kseq->ksq_curr;
472			kseq->ksq_curr = kseq->ksq_next;
473			kseq->ksq_next = swap;
474			continue;
475		}
476		/*
477		 * If we encounter a slice of 0 the kse is in a
478		 * TIMESHARE kse group and its nice was too far out
479		 * of the range that receives slices.
480		 */
481		if (ke->ke_slice == 0) {
482			runq_remove(ke->ke_runq, ke);
483			sched_slice(ke);
484			ke->ke_runq = kseq->ksq_next;
485			runq_add(ke->ke_runq, ke);
486			continue;
487		}
488		return (ke);
489	}
490
491	return (runq_choose(&kseq->ksq_idle));
492}
493
494static void
495kseq_setup(struct kseq *kseq)
496{
497	runq_init(&kseq->ksq_timeshare[0]);
498	runq_init(&kseq->ksq_timeshare[1]);
499	runq_init(&kseq->ksq_idle);
500
501	kseq->ksq_curr = &kseq->ksq_timeshare[0];
502	kseq->ksq_next = &kseq->ksq_timeshare[1];
503
504	kseq->ksq_loads[PRI_ITHD] = 0;
505	kseq->ksq_loads[PRI_REALTIME] = 0;
506	kseq->ksq_loads[PRI_TIMESHARE] = 0;
507	kseq->ksq_loads[PRI_IDLE] = 0;
508	kseq->ksq_load = 0;
509#ifdef SMP
510	kseq->ksq_rslices = 0;
511#endif
512}
513
514static void
515sched_setup(void *dummy)
516{
517	int i;
518
519	slice_min = (hz/100);
520	slice_max = (hz/10);
521
522	mtx_lock_spin(&sched_lock);
523	/* init kseqs */
524	for (i = 0; i < MAXCPU; i++)
525		kseq_setup(KSEQ_CPU(i));
526
527	kseq_add(KSEQ_SELF(), &kse0);
528	mtx_unlock_spin(&sched_lock);
529#ifdef SMP
530	callout_init(&kseq_lb_callout, 1);
531	kseq_balance(NULL);
532#endif
533}
534
535/*
536 * Scale the scheduling priority according to the "interactivity" of this
537 * process.
538 */
539static void
540sched_priority(struct ksegrp *kg)
541{
542	int pri;
543
544	if (kg->kg_pri_class != PRI_TIMESHARE)
545		return;
546
547	pri = SCHED_PRI_INTERACT(sched_interact_score(kg));
548	pri += SCHED_PRI_BASE;
549	pri += kg->kg_nice;
550
551	if (pri > PRI_MAX_TIMESHARE)
552		pri = PRI_MAX_TIMESHARE;
553	else if (pri < PRI_MIN_TIMESHARE)
554		pri = PRI_MIN_TIMESHARE;
555
556	kg->kg_user_pri = pri;
557
558	return;
559}
560
561/*
562 * Calculate a time slice based on the properties of the kseg and the runq
563 * that we're on.  This is only for PRI_TIMESHARE ksegrps.
564 */
565static void
566sched_slice(struct kse *ke)
567{
568	struct kseq *kseq;
569	struct ksegrp *kg;
570
571	kg = ke->ke_ksegrp;
572	kseq = KSEQ_CPU(ke->ke_cpu);
573
574	/*
575	 * Rationale:
576	 * KSEs in interactive ksegs get the minimum slice so that we
577	 * quickly notice if it abuses its advantage.
578	 *
579	 * KSEs in non-interactive ksegs are assigned a slice that is
580	 * based on the ksegs nice value relative to the least nice kseg
581	 * on the run queue for this cpu.
582	 *
583	 * If the KSE is less nice than all others it gets the maximum
584	 * slice and other KSEs will adjust their slice relative to
585	 * this when they first expire.
586	 *
587	 * There is 20 point window that starts relative to the least
588	 * nice kse on the run queue.  Slice size is determined by
589	 * the kse distance from the last nice ksegrp.
590	 *
591	 * If you are outside of the window you will get no slice and
592	 * you will be reevaluated each time you are selected on the
593	 * run queue.
594	 *
595	 */
596
597	if (!SCHED_INTERACTIVE(kg)) {
598		int nice;
599
600		nice = kg->kg_nice + (0 - kseq->ksq_nicemin);
601		if (kseq->ksq_loads[PRI_TIMESHARE] == 0 ||
602		    kg->kg_nice < kseq->ksq_nicemin)
603			ke->ke_slice = SCHED_SLICE_MAX;
604		else if (nice <= SCHED_PRI_NTHRESH)
605			ke->ke_slice = SCHED_SLICE_NICE(nice);
606		else
607			ke->ke_slice = 0;
608	} else
609		ke->ke_slice = SCHED_SLICE_MIN;
610
611	CTR6(KTR_ULE,
612	    "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)",
613	    ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin,
614	    kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg));
615
616	/*
617	 * Check to see if we need to scale back the slp and run time
618	 * in the kg.  This will cause us to forget old interactivity
619	 * while maintaining the current ratio.
620	 */
621	if ((kg->kg_runtime + kg->kg_slptime) >  SCHED_SLP_RUN_MAX) {
622		kg->kg_runtime /= SCHED_SLP_RUN_THROTTLE;
623		kg->kg_slptime /= SCHED_SLP_RUN_THROTTLE;
624	}
625	CTR4(KTR_ULE, "Slp vs Run(2) %p (Slp %d, Run %d, Score %d)",
626	    ke, kg->kg_slptime >> 10, kg->kg_runtime >> 10,
627	    sched_interact_score(kg));
628
629	return;
630}
631
632static int
633sched_interact_score(struct ksegrp *kg)
634{
635	int div;
636
637	if (kg->kg_runtime > kg->kg_slptime) {
638		div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF);
639		return (SCHED_INTERACT_HALF +
640		    (SCHED_INTERACT_HALF - (kg->kg_slptime / div)));
641	} if (kg->kg_slptime > kg->kg_runtime) {
642		div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF);
643		return (kg->kg_runtime / div);
644	}
645
646	/*
647	 * This can happen if slptime and runtime are 0.
648	 */
649	return (0);
650
651}
652
653/*
654 * This is only somewhat accurate since given many processes of the same
655 * priority they will switch when their slices run out, which will be
656 * at most SCHED_SLICE_MAX.
657 */
658int
659sched_rr_interval(void)
660{
661	return (SCHED_SLICE_MAX);
662}
663
664void
665sched_pctcpu_update(struct kse *ke)
666{
667	/*
668	 * Adjust counters and watermark for pctcpu calc.
669	 */
670
671	/*
672	 * Shift the tick count out so that the divide doesn't round away
673	 * our results.
674	 */
675	ke->ke_ticks <<= 10;
676	ke->ke_ticks = (ke->ke_ticks / (ke->ke_ltick - ke->ke_ftick)) *
677		    SCHED_CPU_TICKS;
678	ke->ke_ticks >>= 10;
679	ke->ke_ltick = ticks;
680	ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS;
681}
682
683#ifdef SMP
684/* XXX Should be changed to kseq_load_lowest() */
685int
686sched_pickcpu(void)
687{
688	struct kseq *kseq;
689	int load;
690	int cpu;
691	int i;
692
693	mtx_assert(&sched_lock, MA_OWNED);
694	if (!smp_started)
695		return (0);
696
697	load = 0;
698	cpu = 0;
699
700	for (i = 0; i < mp_maxid; i++) {
701		if (CPU_ABSENT(i))
702			continue;
703		kseq = KSEQ_CPU(i);
704		if (kseq->ksq_load < load) {
705			cpu = i;
706			load = kseq->ksq_load;
707		}
708	}
709
710	CTR1(KTR_RUNQ, "sched_pickcpu: %d", cpu);
711	return (cpu);
712}
713#else
714int
715sched_pickcpu(void)
716{
717	return (0);
718}
719#endif
720
721void
722sched_prio(struct thread *td, u_char prio)
723{
724	struct kse *ke;
725	struct runq *rq;
726
727	mtx_assert(&sched_lock, MA_OWNED);
728	ke = td->td_kse;
729	td->td_priority = prio;
730
731	if (TD_ON_RUNQ(td)) {
732		rq = ke->ke_runq;
733
734		runq_remove(rq, ke);
735		runq_add(rq, ke);
736	}
737}
738
739void
740sched_switchout(struct thread *td)
741{
742	struct kse *ke;
743
744	mtx_assert(&sched_lock, MA_OWNED);
745
746	ke = td->td_kse;
747
748	td->td_last_kse = ke;
749        td->td_lastcpu = td->td_oncpu;
750	td->td_oncpu = NOCPU;
751        td->td_flags &= ~TDF_NEEDRESCHED;
752
753	if (TD_IS_RUNNING(td)) {
754		/*
755		 * This queue is always correct except for idle threads which
756		 * have a higher priority due to priority propagation.
757		 */
758		if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE &&
759		    ke->ke_thread->td_priority > PRI_MIN_IDLE)
760			ke->ke_runq = KSEQ_SELF()->ksq_curr;
761		runq_add(ke->ke_runq, ke);
762		/* setrunqueue(td); */
763		return;
764	}
765	if (ke->ke_runq)
766		kseq_rem(KSEQ_CPU(ke->ke_cpu), ke);
767	/*
768	 * We will not be on the run queue. So we must be
769	 * sleeping or similar.
770	 */
771	if (td->td_proc->p_flag & P_SA)
772		kse_reassign(ke);
773}
774
775void
776sched_switchin(struct thread *td)
777{
778	/* struct kse *ke = td->td_kse; */
779	mtx_assert(&sched_lock, MA_OWNED);
780
781	td->td_oncpu = PCPU_GET(cpuid);
782}
783
784void
785sched_nice(struct ksegrp *kg, int nice)
786{
787	struct kse *ke;
788	struct thread *td;
789	struct kseq *kseq;
790
791	PROC_LOCK_ASSERT(kg->kg_proc, MA_OWNED);
792	mtx_assert(&sched_lock, MA_OWNED);
793	/*
794	 * We need to adjust the nice counts for running KSEs.
795	 */
796	if (kg->kg_pri_class == PRI_TIMESHARE)
797		FOREACH_KSE_IN_GROUP(kg, ke) {
798			if (ke->ke_state != KES_ONRUNQ &&
799			    ke->ke_state != KES_THREAD)
800				continue;
801			kseq = KSEQ_CPU(ke->ke_cpu);
802			kseq_nice_rem(kseq, kg->kg_nice);
803			kseq_nice_add(kseq, nice);
804		}
805	kg->kg_nice = nice;
806	sched_priority(kg);
807	FOREACH_THREAD_IN_GROUP(kg, td)
808		td->td_flags |= TDF_NEEDRESCHED;
809}
810
811void
812sched_sleep(struct thread *td, u_char prio)
813{
814	mtx_assert(&sched_lock, MA_OWNED);
815
816	td->td_slptime = ticks;
817	td->td_priority = prio;
818
819	CTR2(KTR_ULE, "sleep kse %p (tick: %d)",
820	    td->td_kse, td->td_slptime);
821}
822
823void
824sched_wakeup(struct thread *td)
825{
826	mtx_assert(&sched_lock, MA_OWNED);
827
828	/*
829	 * Let the kseg know how long we slept for.  This is because process
830	 * interactivity behavior is modeled in the kseg.
831	 */
832	if (td->td_slptime) {
833		struct ksegrp *kg;
834		int hzticks;
835
836		kg = td->td_ksegrp;
837		hzticks = ticks - td->td_slptime;
838		kg->kg_slptime += hzticks << 10;
839		sched_priority(kg);
840		CTR2(KTR_ULE, "wakeup kse %p (%d ticks)",
841		    td->td_kse, hzticks);
842		td->td_slptime = 0;
843	}
844	setrunqueue(td);
845        if (td->td_priority < curthread->td_priority)
846                curthread->td_flags |= TDF_NEEDRESCHED;
847}
848
849/*
850 * Penalize the parent for creating a new child and initialize the child's
851 * priority.
852 */
853void
854sched_fork(struct proc *p, struct proc *p1)
855{
856
857	mtx_assert(&sched_lock, MA_OWNED);
858
859	sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1));
860	sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1));
861	sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1));
862}
863
864void
865sched_fork_kse(struct kse *ke, struct kse *child)
866{
867
868	child->ke_slice = 1;	/* Attempt to quickly learn interactivity. */
869	child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */
870	child->ke_runq = NULL;
871
872	/*
873	 * Claim that we've been running for one second for statistical
874	 * purposes.
875	 */
876	child->ke_ticks = 0;
877	child->ke_ltick = ticks;
878	child->ke_ftick = ticks - hz;
879}
880
881void
882sched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child)
883{
884
885	PROC_LOCK_ASSERT(child->kg_proc, MA_OWNED);
886	/* XXX Need something better here */
887
888#if 1
889	child->kg_slptime = kg->kg_slptime;
890	child->kg_runtime = kg->kg_runtime;
891#else
892	if (kg->kg_slptime > kg->kg_runtime) {
893		child->kg_slptime = SCHED_DYN_RANGE;
894		child->kg_runtime = kg->kg_slptime / SCHED_DYN_RANGE;
895	} else {
896		child->kg_runtime = SCHED_DYN_RANGE;
897		child->kg_slptime = kg->kg_runtime / SCHED_DYN_RANGE;
898	}
899#endif
900
901	child->kg_user_pri = kg->kg_user_pri;
902	child->kg_nice = kg->kg_nice;
903}
904
905void
906sched_fork_thread(struct thread *td, struct thread *child)
907{
908}
909
910void
911sched_class(struct ksegrp *kg, int class)
912{
913	struct kseq *kseq;
914	struct kse *ke;
915
916	mtx_assert(&sched_lock, MA_OWNED);
917	if (kg->kg_pri_class == class)
918		return;
919
920	FOREACH_KSE_IN_GROUP(kg, ke) {
921		if (ke->ke_state != KES_ONRUNQ &&
922		    ke->ke_state != KES_THREAD)
923			continue;
924		kseq = KSEQ_CPU(ke->ke_cpu);
925
926		kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--;
927		kseq->ksq_loads[PRI_BASE(class)]++;
928
929		if (kg->kg_pri_class == PRI_TIMESHARE)
930			kseq_nice_rem(kseq, kg->kg_nice);
931		else if (class == PRI_TIMESHARE)
932			kseq_nice_add(kseq, kg->kg_nice);
933	}
934
935	kg->kg_pri_class = class;
936}
937
938/*
939 * Return some of the child's priority and interactivity to the parent.
940 */
941void
942sched_exit(struct proc *p, struct proc *child)
943{
944	/* XXX Need something better here */
945	mtx_assert(&sched_lock, MA_OWNED);
946	sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child));
947	sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(child));
948}
949
950void
951sched_exit_kse(struct kse *ke, struct kse *child)
952{
953	kseq_rem(KSEQ_CPU(child->ke_cpu), child);
954}
955
956void
957sched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child)
958{
959	kg->kg_slptime += child->kg_slptime;
960	kg->kg_runtime += child->kg_runtime;
961	if ((kg->kg_runtime + kg->kg_slptime) >  SCHED_SLP_RUN_MAX) {
962		kg->kg_runtime /= SCHED_SLP_RUN_THROTTLE;
963		kg->kg_slptime /= SCHED_SLP_RUN_THROTTLE;
964	}
965}
966
967void
968sched_exit_thread(struct thread *td, struct thread *child)
969{
970}
971
972void
973sched_clock(struct kse *ke)
974{
975	struct kseq *kseq;
976	struct ksegrp *kg;
977	struct thread *td;
978#if 0
979	struct kse *nke;
980#endif
981
982	/*
983	 * sched_setup() apparently happens prior to stathz being set.  We
984	 * need to resolve the timers earlier in the boot so we can avoid
985	 * calculating this here.
986	 */
987	if (realstathz == 0) {
988		realstathz = stathz ? stathz : hz;
989		tickincr = hz / realstathz;
990		/*
991		 * XXX This does not work for values of stathz that are much
992		 * larger than hz.
993		 */
994		if (tickincr == 0)
995			tickincr = 1;
996	}
997
998	td = ke->ke_thread;
999	kg = ke->ke_ksegrp;
1000
1001	mtx_assert(&sched_lock, MA_OWNED);
1002	KASSERT((td != NULL), ("schedclock: null thread pointer"));
1003
1004	/* Adjust ticks for pctcpu */
1005	ke->ke_ticks++;
1006	ke->ke_ltick = ticks;
1007
1008	/* Go up to one second beyond our max and then trim back down */
1009	if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick)
1010		sched_pctcpu_update(ke);
1011
1012	if (td->td_flags & TDF_IDLETD)
1013		return;
1014
1015	CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)",
1016	    ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10);
1017
1018	/*
1019	 * We only do slicing code for TIMESHARE ksegrps.
1020	 */
1021	if (kg->kg_pri_class != PRI_TIMESHARE)
1022		return;
1023	/*
1024	 * Check for a higher priority task on the run queue.  This can happen
1025	 * on SMP if another processor woke up a process on our runq.
1026	 */
1027	kseq = KSEQ_SELF();
1028#if 0
1029	if (kseq->ksq_load > 1 && (nke = kseq_choose(kseq)) != NULL) {
1030		if (sched_strict &&
1031		    nke->ke_thread->td_priority < td->td_priority)
1032			td->td_flags |= TDF_NEEDRESCHED;
1033		else if (nke->ke_thread->td_priority <
1034		    td->td_priority SCHED_PRIO_SLOP)
1035
1036		if (nke->ke_thread->td_priority < td->td_priority)
1037			td->td_flags |= TDF_NEEDRESCHED;
1038	}
1039#endif
1040	/*
1041	 * We used a tick charge it to the ksegrp so that we can compute our
1042	 * interactivity.
1043	 */
1044	kg->kg_runtime += tickincr << 10;
1045
1046	/*
1047	 * We used up one time slice.
1048	 */
1049	ke->ke_slice--;
1050#ifdef SMP
1051	kseq->ksq_rslices--;
1052#endif
1053
1054	if (ke->ke_slice > 0)
1055		return;
1056	/*
1057	 * We're out of time, recompute priorities and requeue.
1058	 */
1059	kseq_rem(kseq, ke);
1060	sched_priority(kg);
1061	sched_slice(ke);
1062	if (SCHED_CURR(kg, ke))
1063		ke->ke_runq = kseq->ksq_curr;
1064	else
1065		ke->ke_runq = kseq->ksq_next;
1066	kseq_add(kseq, ke);
1067	td->td_flags |= TDF_NEEDRESCHED;
1068}
1069
1070int
1071sched_runnable(void)
1072{
1073	struct kseq *kseq;
1074	int load;
1075
1076	load = 1;
1077
1078	mtx_lock_spin(&sched_lock);
1079	kseq = KSEQ_SELF();
1080
1081	if (kseq->ksq_load)
1082		goto out;
1083#ifdef SMP
1084	/*
1085	 * For SMP we may steal other processor's KSEs.  Just search until we
1086	 * verify that at least on other cpu has a runnable task.
1087	 */
1088	if (smp_started) {
1089		int i;
1090
1091		for (i = 0; i < mp_maxid; i++) {
1092			if (CPU_ABSENT(i))
1093				continue;
1094			kseq = KSEQ_CPU(i);
1095			if (kseq->ksq_load > 1)
1096				goto out;
1097		}
1098	}
1099#endif
1100	load = 0;
1101out:
1102	mtx_unlock_spin(&sched_lock);
1103	return (load);
1104}
1105
1106void
1107sched_userret(struct thread *td)
1108{
1109	struct ksegrp *kg;
1110	struct kseq *kseq;
1111	struct kse *ke;
1112
1113	kg = td->td_ksegrp;
1114
1115	if (td->td_priority != kg->kg_user_pri) {
1116		mtx_lock_spin(&sched_lock);
1117		td->td_priority = kg->kg_user_pri;
1118		kseq = KSEQ_SELF();
1119		if (td->td_ksegrp->kg_pri_class == PRI_TIMESHARE &&
1120		    kseq->ksq_load > 1 &&
1121		    (ke = kseq_choose(kseq)) != NULL &&
1122		    ke->ke_thread->td_priority < td->td_priority)
1123			curthread->td_flags |= TDF_NEEDRESCHED;
1124		mtx_unlock_spin(&sched_lock);
1125	}
1126}
1127
1128struct kse *
1129sched_choose(void)
1130{
1131	struct kseq *kseq;
1132	struct kse *ke;
1133
1134	mtx_assert(&sched_lock, MA_OWNED);
1135#ifdef SMP
1136retry:
1137#endif
1138	kseq = KSEQ_SELF();
1139	ke = kseq_choose(kseq);
1140	if (ke) {
1141		runq_remove(ke->ke_runq, ke);
1142		ke->ke_state = KES_THREAD;
1143
1144		if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) {
1145			CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)",
1146			    ke, ke->ke_runq, ke->ke_slice,
1147			    ke->ke_thread->td_priority);
1148		}
1149		return (ke);
1150	}
1151
1152#ifdef SMP
1153	if (smp_started) {
1154		/*
1155		 * Find the cpu with the highest load and steal one proc.
1156		 */
1157		if ((kseq = kseq_load_highest()) == NULL)
1158			return (NULL);
1159
1160		/*
1161		 * Remove this kse from this kseq and runq and then requeue
1162		 * on the current processor.  Then we will dequeue it
1163		 * normally above.
1164		 */
1165		kseq_move(kseq, PCPU_GET(cpuid));
1166		goto retry;
1167	}
1168#endif
1169
1170	return (NULL);
1171}
1172
1173void
1174sched_add(struct kse *ke)
1175{
1176	struct kseq *kseq;
1177	struct ksegrp *kg;
1178
1179	mtx_assert(&sched_lock, MA_OWNED);
1180	KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE"));
1181	KASSERT((ke->ke_thread->td_kse != NULL),
1182	    ("sched_add: No KSE on thread"));
1183	KASSERT(ke->ke_state != KES_ONRUNQ,
1184	    ("sched_add: kse %p (%s) already in run queue", ke,
1185	    ke->ke_proc->p_comm));
1186	KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
1187	    ("sched_add: process swapped out"));
1188	KASSERT(ke->ke_runq == NULL,
1189	    ("sched_add: KSE %p is still assigned to a run queue", ke));
1190
1191	kg = ke->ke_ksegrp;
1192
1193	switch (PRI_BASE(kg->kg_pri_class)) {
1194	case PRI_ITHD:
1195	case PRI_REALTIME:
1196		kseq = KSEQ_SELF();
1197		ke->ke_runq = kseq->ksq_curr;
1198		ke->ke_slice = SCHED_SLICE_MAX;
1199		ke->ke_cpu = PCPU_GET(cpuid);
1200		break;
1201	case PRI_TIMESHARE:
1202		kseq = KSEQ_CPU(ke->ke_cpu);
1203		if (SCHED_CURR(kg, ke))
1204			ke->ke_runq = kseq->ksq_curr;
1205		else
1206			ke->ke_runq = kseq->ksq_next;
1207		break;
1208	case PRI_IDLE:
1209		kseq = KSEQ_CPU(ke->ke_cpu);
1210		/*
1211		 * This is for priority prop.
1212		 */
1213		if (ke->ke_thread->td_priority > PRI_MIN_IDLE)
1214			ke->ke_runq = kseq->ksq_curr;
1215		else
1216			ke->ke_runq = &kseq->ksq_idle;
1217		ke->ke_slice = SCHED_SLICE_MIN;
1218		break;
1219	default:
1220		panic("Unknown pri class.\n");
1221		break;
1222	}
1223
1224	ke->ke_ksegrp->kg_runq_kses++;
1225	ke->ke_state = KES_ONRUNQ;
1226
1227	runq_add(ke->ke_runq, ke);
1228	kseq_add(kseq, ke);
1229}
1230
1231void
1232sched_rem(struct kse *ke)
1233{
1234	struct kseq *kseq;
1235
1236	mtx_assert(&sched_lock, MA_OWNED);
1237	KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue"));
1238
1239	ke->ke_state = KES_THREAD;
1240	ke->ke_ksegrp->kg_runq_kses--;
1241	kseq = KSEQ_CPU(ke->ke_cpu);
1242	runq_remove(ke->ke_runq, ke);
1243	kseq_rem(kseq, ke);
1244}
1245
1246fixpt_t
1247sched_pctcpu(struct kse *ke)
1248{
1249	fixpt_t pctcpu;
1250
1251	pctcpu = 0;
1252
1253	mtx_lock_spin(&sched_lock);
1254	if (ke->ke_ticks) {
1255		int rtick;
1256
1257		/* Update to account for time potentially spent sleeping */
1258		ke->ke_ltick = ticks;
1259		/*
1260		 * Don't update more frequently than twice a second.  Allowing
1261		 * this causes the cpu usage to decay away too quickly due to
1262		 * rounding errors.
1263		 */
1264		if (ke->ke_ltick < (ticks - (hz / 2)))
1265			sched_pctcpu_update(ke);
1266
1267		/* How many rtick per second ? */
1268		rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS);
1269		pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT;
1270	}
1271
1272	ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick;
1273	mtx_unlock_spin(&sched_lock);
1274
1275	return (pctcpu);
1276}
1277
1278int
1279sched_sizeof_kse(void)
1280{
1281	return (sizeof(struct kse) + sizeof(struct ke_sched));
1282}
1283
1284int
1285sched_sizeof_ksegrp(void)
1286{
1287	return (sizeof(struct ksegrp) + sizeof(struct kg_sched));
1288}
1289
1290int
1291sched_sizeof_proc(void)
1292{
1293	return (sizeof(struct proc));
1294}
1295
1296int
1297sched_sizeof_thread(void)
1298{
1299	return (sizeof(struct thread) + sizeof(struct td_sched));
1300}
1301