sched_ule.c revision 121790
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 121790 2003-10-31 11:16:04Z 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#include <machine/smp.h>
54
55#define KTR_ULE         KTR_NFS
56
57/* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
58/* XXX This is bogus compatability crap for ps */
59static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
60SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
61
62static void sched_setup(void *dummy);
63SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
64
65static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED");
66
67static int sched_strict;
68SYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, "");
69
70static int slice_min = 1;
71SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, "");
72
73static int slice_max = 10;
74SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, "");
75
76int realstathz;
77int tickincr = 1;
78
79#ifdef SMP
80/* Callout to handle load balancing SMP systems. */
81static struct callout kseq_lb_callout;
82#endif
83
84/*
85 * These datastructures are allocated within their parent datastructure but
86 * are scheduler specific.
87 */
88
89struct ke_sched {
90	int		ske_slice;
91	struct runq	*ske_runq;
92	/* The following variables are only used for pctcpu calculation */
93	int		ske_ltick;	/* Last tick that we were running on */
94	int		ske_ftick;	/* First tick that we were running on */
95	int		ske_ticks;	/* Tick count */
96	/* CPU that we have affinity for. */
97	u_char		ske_cpu;
98};
99#define	ke_slice	ke_sched->ske_slice
100#define	ke_runq		ke_sched->ske_runq
101#define	ke_ltick	ke_sched->ske_ltick
102#define	ke_ftick	ke_sched->ske_ftick
103#define	ke_ticks	ke_sched->ske_ticks
104#define	ke_cpu		ke_sched->ske_cpu
105#define	ke_assign	ke_procq.tqe_next
106
107#define	KEF_ASSIGNED	KEF_SCHED0	/* KSE is being migrated. */
108
109struct kg_sched {
110	int	skg_slptime;		/* Number of ticks we vol. slept */
111	int	skg_runtime;		/* Number of ticks we were running */
112};
113#define	kg_slptime	kg_sched->skg_slptime
114#define	kg_runtime	kg_sched->skg_runtime
115
116struct td_sched {
117	int	std_slptime;
118};
119#define	td_slptime	td_sched->std_slptime
120
121struct td_sched td_sched;
122struct ke_sched ke_sched;
123struct kg_sched kg_sched;
124
125struct ke_sched *kse0_sched = &ke_sched;
126struct kg_sched *ksegrp0_sched = &kg_sched;
127struct p_sched *proc0_sched = NULL;
128struct td_sched *thread0_sched = &td_sched;
129
130/*
131 * The priority is primarily determined by the interactivity score.  Thus, we
132 * give lower(better) priorities to kse groups that use less CPU.  The nice
133 * value is then directly added to this to allow nice to have some effect
134 * on latency.
135 *
136 * PRI_RANGE:	Total priority range for timeshare threads.
137 * PRI_NRESV:	Number of nice values.
138 * PRI_BASE:	The start of the dynamic range.
139 */
140#define	SCHED_PRI_RANGE		(PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
141#define	SCHED_PRI_NRESV		PRIO_TOTAL
142#define	SCHED_PRI_NHALF		(PRIO_TOTAL / 2)
143#define	SCHED_PRI_NTHRESH	(SCHED_PRI_NHALF - 1)
144#define	SCHED_PRI_BASE		(PRI_MIN_TIMESHARE)
145#define	SCHED_PRI_INTERACT(score)					\
146    ((score) * SCHED_PRI_RANGE / SCHED_INTERACT_MAX)
147
148/*
149 * These determine the interactivity of a process.
150 *
151 * SLP_RUN_MAX:	Maximum amount of sleep time + run time we'll accumulate
152 *		before throttling back.
153 * SLP_RUN_THROTTLE:	Divisor for reducing slp/run time at fork time.
154 * INTERACT_MAX:	Maximum interactivity value.  Smaller is better.
155 * INTERACT_THRESH:	Threshhold for placement on the current runq.
156 */
157#define	SCHED_SLP_RUN_MAX	((hz * 5) << 10)
158#define	SCHED_SLP_RUN_THROTTLE	(100)
159#define	SCHED_INTERACT_MAX	(100)
160#define	SCHED_INTERACT_HALF	(SCHED_INTERACT_MAX / 2)
161#define	SCHED_INTERACT_THRESH	(30)
162
163/*
164 * These parameters and macros determine the size of the time slice that is
165 * granted to each thread.
166 *
167 * SLICE_MIN:	Minimum time slice granted, in units of ticks.
168 * SLICE_MAX:	Maximum time slice granted.
169 * SLICE_RANGE:	Range of available time slices scaled by hz.
170 * SLICE_SCALE:	The number slices granted per val in the range of [0, max].
171 * SLICE_NICE:  Determine the amount of slice granted to a scaled nice.
172 */
173#define	SCHED_SLICE_MIN			(slice_min)
174#define	SCHED_SLICE_MAX			(slice_max)
175#define	SCHED_SLICE_RANGE		(SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1)
176#define	SCHED_SLICE_SCALE(val, max)	(((val) * SCHED_SLICE_RANGE) / (max))
177#define	SCHED_SLICE_NICE(nice)						\
178    (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_PRI_NTHRESH))
179
180/*
181 * This macro determines whether or not the kse belongs on the current or
182 * next run queue.
183 *
184 * XXX nice value should effect how interactive a kg is.
185 */
186#define	SCHED_INTERACTIVE(kg)						\
187    (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
188#define	SCHED_CURR(kg, ke)						\
189    (ke->ke_thread->td_priority != kg->kg_user_pri ||			\
190    SCHED_INTERACTIVE(kg))
191
192/*
193 * Cpu percentage computation macros and defines.
194 *
195 * SCHED_CPU_TIME:	Number of seconds to average the cpu usage across.
196 * SCHED_CPU_TICKS:	Number of hz ticks to average the cpu usage across.
197 */
198
199#define	SCHED_CPU_TIME	10
200#define	SCHED_CPU_TICKS	(hz * SCHED_CPU_TIME)
201
202/*
203 * kseq - per processor runqs and statistics.
204 */
205
206#define	KSEQ_NCLASS	(PRI_IDLE + 1)	/* Number of run classes. */
207
208struct kseq {
209	struct runq	ksq_idle;		/* Queue of IDLE threads. */
210	struct runq	ksq_timeshare[2];	/* Run queues for !IDLE. */
211	struct runq	*ksq_next;		/* Next timeshare queue. */
212	struct runq	*ksq_curr;		/* Current queue. */
213	int		ksq_loads[KSEQ_NCLASS];	/* Load for each class */
214	int		ksq_load;		/* Aggregate load. */
215	short		ksq_nice[PRIO_TOTAL + 1]; /* KSEs in each nice bin. */
216	short		ksq_nicemin;		/* Least nice. */
217#ifdef SMP
218	unsigned int	ksq_rslices;	/* Slices on run queue */
219	int		ksq_cpus;	/* Count of CPUs in this kseq. */
220	struct kse 	*ksq_assigned;	/* KSEs assigned by another CPU. */
221#endif
222};
223
224/*
225 * One kse queue per processor.
226 */
227#ifdef SMP
228static int kseq_idle;
229static struct kseq	kseq_cpu[MAXCPU];
230static struct kseq	*kseq_idmap[MAXCPU];
231#define	KSEQ_SELF()	(kseq_idmap[PCPU_GET(cpuid)])
232#define	KSEQ_CPU(x)	(kseq_idmap[(x)])
233#else
234static struct kseq	kseq_cpu;
235#define	KSEQ_SELF()	(&kseq_cpu)
236#define	KSEQ_CPU(x)	(&kseq_cpu)
237#endif
238
239static void sched_slice(struct kse *ke);
240static void sched_priority(struct ksegrp *kg);
241static int sched_interact_score(struct ksegrp *kg);
242static void sched_interact_update(struct ksegrp *kg);
243static void sched_pctcpu_update(struct kse *ke);
244
245/* Operations on per processor queues */
246static struct kse * kseq_choose(struct kseq *kseq);
247static void kseq_setup(struct kseq *kseq);
248static void kseq_add(struct kseq *kseq, struct kse *ke);
249static void kseq_rem(struct kseq *kseq, struct kse *ke);
250static void kseq_nice_add(struct kseq *kseq, int nice);
251static void kseq_nice_rem(struct kseq *kseq, int nice);
252void kseq_print(int cpu);
253#ifdef SMP
254#if 0
255static int sched_pickcpu(void);
256#endif
257static struct kse *runq_steal(struct runq *rq);
258static struct kseq *kseq_load_highest(void);
259static void kseq_balance(void *arg);
260static void kseq_move(struct kseq *from, int cpu);
261static int kseq_find(void);
262static void kseq_notify(struct kse *ke, int cpu);
263static void kseq_assign(struct kseq *);
264static struct kse *kseq_steal(struct kseq *kseq);
265#endif
266
267void
268kseq_print(int cpu)
269{
270	struct kseq *kseq;
271	int i;
272
273	kseq = KSEQ_CPU(cpu);
274
275	printf("kseq:\n");
276	printf("\tload:           %d\n", kseq->ksq_load);
277	printf("\tload ITHD:      %d\n", kseq->ksq_loads[PRI_ITHD]);
278	printf("\tload REALTIME:  %d\n", kseq->ksq_loads[PRI_REALTIME]);
279	printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]);
280	printf("\tload IDLE:      %d\n", kseq->ksq_loads[PRI_IDLE]);
281	printf("\tnicemin:\t%d\n", kseq->ksq_nicemin);
282	printf("\tnice counts:\n");
283	for (i = 0; i < PRIO_TOTAL + 1; i++)
284		if (kseq->ksq_nice[i])
285			printf("\t\t%d = %d\n",
286			    i - SCHED_PRI_NHALF, kseq->ksq_nice[i]);
287}
288
289static void
290kseq_add(struct kseq *kseq, struct kse *ke)
291{
292	mtx_assert(&sched_lock, MA_OWNED);
293	kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++;
294	kseq->ksq_load++;
295	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
296	CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))",
297	    ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority,
298	    ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin);
299	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
300		kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice);
301#ifdef SMP
302	kseq->ksq_rslices += ke->ke_slice;
303#endif
304}
305
306static void
307kseq_rem(struct kseq *kseq, struct kse *ke)
308{
309	mtx_assert(&sched_lock, MA_OWNED);
310	kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--;
311	kseq->ksq_load--;
312	ke->ke_runq = NULL;
313	if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
314		kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice);
315#ifdef SMP
316	kseq->ksq_rslices -= ke->ke_slice;
317#endif
318}
319
320static void
321kseq_nice_add(struct kseq *kseq, int nice)
322{
323	mtx_assert(&sched_lock, MA_OWNED);
324	/* Normalize to zero. */
325	kseq->ksq_nice[nice + SCHED_PRI_NHALF]++;
326	if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 1)
327		kseq->ksq_nicemin = nice;
328}
329
330static void
331kseq_nice_rem(struct kseq *kseq, int nice)
332{
333	int n;
334
335	mtx_assert(&sched_lock, MA_OWNED);
336	/* Normalize to zero. */
337	n = nice + SCHED_PRI_NHALF;
338	kseq->ksq_nice[n]--;
339	KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count."));
340
341	/*
342	 * If this wasn't the smallest nice value or there are more in
343	 * this bucket we can just return.  Otherwise we have to recalculate
344	 * the smallest nice.
345	 */
346	if (nice != kseq->ksq_nicemin ||
347	    kseq->ksq_nice[n] != 0 ||
348	    kseq->ksq_loads[PRI_TIMESHARE] == 0)
349		return;
350
351	for (; n < SCHED_PRI_NRESV + 1; n++)
352		if (kseq->ksq_nice[n]) {
353			kseq->ksq_nicemin = n - SCHED_PRI_NHALF;
354			return;
355		}
356}
357
358#ifdef SMP
359/*
360 * kseq_balance is a simple CPU load balancing algorithm.  It operates by
361 * finding the least loaded and most loaded cpu and equalizing their load
362 * by migrating some processes.
363 *
364 * Dealing only with two CPUs at a time has two advantages.  Firstly, most
365 * installations will only have 2 cpus.  Secondly, load balancing too much at
366 * once can have an unpleasant effect on the system.  The scheduler rarely has
367 * enough information to make perfect decisions.  So this algorithm chooses
368 * algorithm simplicity and more gradual effects on load in larger systems.
369 *
370 * It could be improved by considering the priorities and slices assigned to
371 * each task prior to balancing them.  There are many pathological cases with
372 * any approach and so the semi random algorithm below may work as well as any.
373 *
374 */
375static void
376kseq_balance(void *arg)
377{
378	struct kseq *kseq;
379	int high_load;
380	int low_load;
381	int high_cpu;
382	int low_cpu;
383	int move;
384	int diff;
385	int i;
386
387	high_cpu = 0;
388	low_cpu = 0;
389	high_load = 0;
390	low_load = -1;
391
392	mtx_lock_spin(&sched_lock);
393	if (smp_started == 0)
394		goto out;
395
396	for (i = 0; i < mp_maxid; i++) {
397		if (CPU_ABSENT(i) || (i & stopped_cpus) != 0)
398			continue;
399		kseq = KSEQ_CPU(i);
400		if (kseq->ksq_load > high_load) {
401			high_load = kseq->ksq_load;
402			high_cpu = i;
403		}
404		if (low_load == -1 || kseq->ksq_load < low_load) {
405			low_load = kseq->ksq_load;
406			low_cpu = i;
407		}
408	}
409
410	kseq = KSEQ_CPU(high_cpu);
411
412	high_load = kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] +
413	    kseq->ksq_loads[PRI_REALTIME];
414	/*
415	 * Nothing to do.
416	 */
417	if (high_load < kseq->ksq_cpus + 1)
418		goto out;
419
420	high_load -= kseq->ksq_cpus;
421
422	if (low_load >= high_load)
423		goto out;
424
425	diff = high_load - low_load;
426	move = diff / 2;
427	if (diff & 0x1)
428		move++;
429
430	for (i = 0; i < move; i++)
431		kseq_move(kseq, low_cpu);
432
433out:
434	mtx_unlock_spin(&sched_lock);
435	callout_reset(&kseq_lb_callout, hz, kseq_balance, NULL);
436
437	return;
438}
439
440static struct kseq *
441kseq_load_highest(void)
442{
443	struct kseq *kseq;
444	int load;
445	int cpu;
446	int i;
447
448	mtx_assert(&sched_lock, MA_OWNED);
449	cpu = 0;
450	load = 0;
451
452	for (i = 0; i < mp_maxid; i++) {
453		if (CPU_ABSENT(i) || (i & stopped_cpus) != 0)
454			continue;
455		kseq = KSEQ_CPU(i);
456		if (kseq->ksq_load > load) {
457			load = kseq->ksq_load;
458			cpu = i;
459		}
460	}
461	kseq = KSEQ_CPU(cpu);
462
463	if ((kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] +
464	    kseq->ksq_loads[PRI_REALTIME]) > kseq->ksq_cpus)
465		return (kseq);
466
467	return (NULL);
468}
469
470static void
471kseq_move(struct kseq *from, int cpu)
472{
473	struct kse *ke;
474
475	ke = kseq_steal(from);
476	runq_remove(ke->ke_runq, ke);
477	ke->ke_state = KES_THREAD;
478	kseq_rem(from, ke);
479
480	ke->ke_cpu = cpu;
481	sched_add(ke->ke_thread);
482}
483
484static int
485kseq_find(void)
486{
487	struct kseq *high;
488
489	if (!smp_started)
490		return (0);
491	if (kseq_idle & PCPU_GET(cpumask))
492		return (0);
493	/*
494	 * Find the cpu with the highest load and steal one proc.
495	 */
496	if ((high = kseq_load_highest()) == NULL ||
497	    high == KSEQ_SELF()) {
498		/*
499		 * If we couldn't find one, set ourselves in the
500		 * idle map.
501		 */
502		atomic_set_int(&kseq_idle, PCPU_GET(cpumask));
503		return (0);
504	}
505	/*
506	 * Remove this kse from this kseq and runq and then requeue
507	 * on the current processor.  We now have a load of one!
508	 */
509	kseq_move(high, PCPU_GET(cpuid));
510
511	return (1);
512}
513
514static void
515kseq_assign(struct kseq *kseq)
516{
517	struct kse *nke;
518	struct kse *ke;
519
520	do {
521		ke = kseq->ksq_assigned;
522	} while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke, NULL));
523	for (; ke != NULL; ke = nke) {
524		nke = ke->ke_assign;
525		ke->ke_flags &= ~KEF_ASSIGNED;
526		sched_add(ke->ke_thread);
527	}
528}
529
530static void
531kseq_notify(struct kse *ke, int cpu)
532{
533	struct kseq *kseq;
534	struct thread *td;
535	struct pcpu *pcpu;
536
537	ke->ke_flags |= KEF_ASSIGNED;
538
539	kseq = KSEQ_CPU(cpu);
540
541	/*
542	 * Place a KSE on another cpu's queue and force a resched.
543	 */
544	do {
545		ke->ke_assign = kseq->ksq_assigned;
546	} while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke->ke_assign, ke));
547	pcpu = pcpu_find(cpu);
548	td = pcpu->pc_curthread;
549	if (ke->ke_thread->td_priority < td->td_priority ||
550	    td == pcpu->pc_idlethread) {
551		td->td_flags |= TDF_NEEDRESCHED;
552		ipi_selected(1 << cpu, IPI_AST);
553	}
554}
555
556static struct kse *
557runq_steal(struct runq *rq)
558{
559	struct rqhead *rqh;
560	struct rqbits *rqb;
561	struct kse *ke;
562	int word;
563	int bit;
564
565	mtx_assert(&sched_lock, MA_OWNED);
566	rqb = &rq->rq_status;
567	for (word = 0; word < RQB_LEN; word++) {
568		if (rqb->rqb_bits[word] == 0)
569			continue;
570		for (bit = 0; bit < RQB_BPW; bit++) {
571			if ((rqb->rqb_bits[word] & (1 << bit)) == 0)
572				continue;
573			rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
574			TAILQ_FOREACH(ke, rqh, ke_procq) {
575				if (PRI_BASE(ke->ke_ksegrp->kg_pri_class) !=
576				    PRI_ITHD)
577					return (ke);
578			}
579		}
580	}
581	return (NULL);
582}
583
584static struct kse *
585kseq_steal(struct kseq *kseq)
586{
587	struct kse *ke;
588
589	if ((ke = runq_steal(kseq->ksq_curr)) != NULL)
590		return (ke);
591	if ((ke = runq_steal(kseq->ksq_next)) != NULL)
592		return (ke);
593	return (runq_steal(&kseq->ksq_idle));
594}
595#endif	/* SMP */
596
597/*
598 * Pick the highest priority task we have and return it.
599 */
600
601static struct kse *
602kseq_choose(struct kseq *kseq)
603{
604	struct kse *ke;
605	struct runq *swap;
606
607	mtx_assert(&sched_lock, MA_OWNED);
608	swap = NULL;
609
610	for (;;) {
611		ke = runq_choose(kseq->ksq_curr);
612		if (ke == NULL) {
613			/*
614			 * We already swaped once and didn't get anywhere.
615			 */
616			if (swap)
617				break;
618			swap = kseq->ksq_curr;
619			kseq->ksq_curr = kseq->ksq_next;
620			kseq->ksq_next = swap;
621			continue;
622		}
623		/*
624		 * If we encounter a slice of 0 the kse is in a
625		 * TIMESHARE kse group and its nice was too far out
626		 * of the range that receives slices.
627		 */
628		if (ke->ke_slice == 0) {
629			runq_remove(ke->ke_runq, ke);
630			sched_slice(ke);
631			ke->ke_runq = kseq->ksq_next;
632			runq_add(ke->ke_runq, ke);
633			continue;
634		}
635		return (ke);
636	}
637
638	return (runq_choose(&kseq->ksq_idle));
639}
640
641static void
642kseq_setup(struct kseq *kseq)
643{
644	runq_init(&kseq->ksq_timeshare[0]);
645	runq_init(&kseq->ksq_timeshare[1]);
646	runq_init(&kseq->ksq_idle);
647
648	kseq->ksq_curr = &kseq->ksq_timeshare[0];
649	kseq->ksq_next = &kseq->ksq_timeshare[1];
650
651	kseq->ksq_loads[PRI_ITHD] = 0;
652	kseq->ksq_loads[PRI_REALTIME] = 0;
653	kseq->ksq_loads[PRI_TIMESHARE] = 0;
654	kseq->ksq_loads[PRI_IDLE] = 0;
655	kseq->ksq_load = 0;
656#ifdef SMP
657	kseq->ksq_rslices = 0;
658	kseq->ksq_assigned = NULL;
659#endif
660}
661
662static void
663sched_setup(void *dummy)
664{
665#ifdef SMP
666	int i;
667#endif
668
669	slice_min = (hz/100);	/* 10ms */
670	slice_max = (hz/7);	/* ~140ms */
671
672#ifdef SMP
673	/* init kseqs */
674	/* Create the idmap. */
675#ifdef ULE_HTT_EXPERIMENTAL
676	if (smp_topology == NULL) {
677#else
678	if (1) {
679#endif
680		for (i = 0; i < MAXCPU; i++) {
681			kseq_setup(&kseq_cpu[i]);
682			kseq_idmap[i] = &kseq_cpu[i];
683			kseq_cpu[i].ksq_cpus = 1;
684		}
685	} else {
686		int j;
687
688		for (i = 0; i < smp_topology->ct_count; i++) {
689			struct cpu_group *cg;
690
691			cg = &smp_topology->ct_group[i];
692			kseq_setup(&kseq_cpu[i]);
693
694			for (j = 0; j < MAXCPU; j++)
695				if ((cg->cg_mask & (1 << j)) != 0)
696					kseq_idmap[j] = &kseq_cpu[i];
697			kseq_cpu[i].ksq_cpus = cg->cg_count;
698		}
699	}
700	callout_init(&kseq_lb_callout, CALLOUT_MPSAFE);
701	kseq_balance(NULL);
702#else
703	kseq_setup(KSEQ_SELF());
704#endif
705	mtx_lock_spin(&sched_lock);
706	kseq_add(KSEQ_SELF(), &kse0);
707	mtx_unlock_spin(&sched_lock);
708}
709
710/*
711 * Scale the scheduling priority according to the "interactivity" of this
712 * process.
713 */
714static void
715sched_priority(struct ksegrp *kg)
716{
717	int pri;
718
719	if (kg->kg_pri_class != PRI_TIMESHARE)
720		return;
721
722	pri = SCHED_PRI_INTERACT(sched_interact_score(kg));
723	pri += SCHED_PRI_BASE;
724	pri += kg->kg_nice;
725
726	if (pri > PRI_MAX_TIMESHARE)
727		pri = PRI_MAX_TIMESHARE;
728	else if (pri < PRI_MIN_TIMESHARE)
729		pri = PRI_MIN_TIMESHARE;
730
731	kg->kg_user_pri = pri;
732
733	return;
734}
735
736/*
737 * Calculate a time slice based on the properties of the kseg and the runq
738 * that we're on.  This is only for PRI_TIMESHARE ksegrps.
739 */
740static void
741sched_slice(struct kse *ke)
742{
743	struct kseq *kseq;
744	struct ksegrp *kg;
745
746	kg = ke->ke_ksegrp;
747	kseq = KSEQ_CPU(ke->ke_cpu);
748
749	/*
750	 * Rationale:
751	 * KSEs in interactive ksegs get the minimum slice so that we
752	 * quickly notice if it abuses its advantage.
753	 *
754	 * KSEs in non-interactive ksegs are assigned a slice that is
755	 * based on the ksegs nice value relative to the least nice kseg
756	 * on the run queue for this cpu.
757	 *
758	 * If the KSE is less nice than all others it gets the maximum
759	 * slice and other KSEs will adjust their slice relative to
760	 * this when they first expire.
761	 *
762	 * There is 20 point window that starts relative to the least
763	 * nice kse on the run queue.  Slice size is determined by
764	 * the kse distance from the last nice ksegrp.
765	 *
766	 * If you are outside of the window you will get no slice and
767	 * you will be reevaluated each time you are selected on the
768	 * run queue.
769	 *
770	 */
771
772	if (!SCHED_INTERACTIVE(kg)) {
773		int nice;
774
775		nice = kg->kg_nice + (0 - kseq->ksq_nicemin);
776		if (kseq->ksq_loads[PRI_TIMESHARE] == 0 ||
777		    kg->kg_nice < kseq->ksq_nicemin)
778			ke->ke_slice = SCHED_SLICE_MAX;
779		else if (nice <= SCHED_PRI_NTHRESH)
780			ke->ke_slice = SCHED_SLICE_NICE(nice);
781		else
782			ke->ke_slice = 0;
783	} else
784		ke->ke_slice = SCHED_SLICE_MIN;
785
786	CTR6(KTR_ULE,
787	    "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)",
788	    ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin,
789	    kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg));
790
791	/*
792	 * Check to see if we need to scale back the slp and run time
793	 * in the kg.  This will cause us to forget old interactivity
794	 * while maintaining the current ratio.
795	 */
796	sched_interact_update(kg);
797
798	return;
799}
800
801static void
802sched_interact_update(struct ksegrp *kg)
803{
804        int ratio;
805
806	if ((kg->kg_runtime + kg->kg_slptime) > SCHED_SLP_RUN_MAX) {
807		ratio = ((SCHED_SLP_RUN_MAX * 15) / (kg->kg_runtime +
808		    kg->kg_slptime ));
809		kg->kg_runtime = (kg->kg_runtime * ratio) / 16;
810		kg->kg_slptime = (kg->kg_slptime * ratio) / 16;
811	}
812}
813
814static int
815sched_interact_score(struct ksegrp *kg)
816{
817	int div;
818
819	if (kg->kg_runtime > kg->kg_slptime) {
820		div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF);
821		return (SCHED_INTERACT_HALF +
822		    (SCHED_INTERACT_HALF - (kg->kg_slptime / div)));
823	} if (kg->kg_slptime > kg->kg_runtime) {
824		div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF);
825		return (kg->kg_runtime / div);
826	}
827
828	/*
829	 * This can happen if slptime and runtime are 0.
830	 */
831	return (0);
832
833}
834
835/*
836 * This is only somewhat accurate since given many processes of the same
837 * priority they will switch when their slices run out, which will be
838 * at most SCHED_SLICE_MAX.
839 */
840int
841sched_rr_interval(void)
842{
843	return (SCHED_SLICE_MAX);
844}
845
846static void
847sched_pctcpu_update(struct kse *ke)
848{
849	/*
850	 * Adjust counters and watermark for pctcpu calc.
851	 */
852	if (ke->ke_ltick > ticks - SCHED_CPU_TICKS) {
853		/*
854		 * Shift the tick count out so that the divide doesn't
855		 * round away our results.
856		 */
857		ke->ke_ticks <<= 10;
858		ke->ke_ticks = (ke->ke_ticks / (ticks - ke->ke_ftick)) *
859			    SCHED_CPU_TICKS;
860		ke->ke_ticks >>= 10;
861	} else
862		ke->ke_ticks = 0;
863	ke->ke_ltick = ticks;
864	ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS;
865}
866
867#if 0
868/* XXX Should be changed to kseq_load_lowest() */
869int
870sched_pickcpu(void)
871{
872	struct kseq *kseq;
873	int load;
874	int cpu;
875	int i;
876
877	mtx_assert(&sched_lock, MA_OWNED);
878	if (!smp_started)
879		return (0);
880
881	load = 0;
882	cpu = 0;
883
884	for (i = 0; i < mp_maxid; i++) {
885		if (CPU_ABSENT(i) || (i & stopped_cpus) != 0)
886			continue;
887		kseq = KSEQ_CPU(i);
888		if (kseq->ksq_load < load) {
889			cpu = i;
890			load = kseq->ksq_load;
891		}
892	}
893
894	CTR1(KTR_RUNQ, "sched_pickcpu: %d", cpu);
895	return (cpu);
896}
897#endif
898
899void
900sched_prio(struct thread *td, u_char prio)
901{
902	struct kse *ke;
903
904	ke = td->td_kse;
905	mtx_assert(&sched_lock, MA_OWNED);
906	if (TD_ON_RUNQ(td)) {
907		/*
908		 * If the priority has been elevated due to priority
909		 * propagation, we may have to move ourselves to a new
910		 * queue.  We still call adjustrunqueue below in case kse
911		 * needs to fix things up.
912		 */
913		if (ke && (ke->ke_flags & KEF_ASSIGNED) == 0 &&
914		    ke->ke_runq != KSEQ_CPU(ke->ke_cpu)->ksq_curr) {
915			runq_remove(ke->ke_runq, ke);
916			ke->ke_runq = KSEQ_CPU(ke->ke_cpu)->ksq_curr;
917			runq_add(ke->ke_runq, ke);
918		}
919		adjustrunqueue(td, prio);
920	} else
921		td->td_priority = prio;
922}
923
924void
925sched_switch(struct thread *td)
926{
927	struct thread *newtd;
928	struct kse *ke;
929
930	mtx_assert(&sched_lock, MA_OWNED);
931
932	ke = td->td_kse;
933
934	td->td_last_kse = ke;
935        td->td_lastcpu = td->td_oncpu;
936	td->td_oncpu = NOCPU;
937        td->td_flags &= ~TDF_NEEDRESCHED;
938
939	if (TD_IS_RUNNING(td)) {
940		if (td->td_proc->p_flag & P_SA) {
941			kseq_rem(KSEQ_CPU(ke->ke_cpu), ke);
942			setrunqueue(td);
943		} else {
944			/*
945			 * This queue is always correct except for idle threads
946			 * which have a higher priority due to priority
947			 * propagation.
948			 */
949			if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE) {
950				if (td->td_priority < PRI_MIN_IDLE)
951					ke->ke_runq = KSEQ_SELF()->ksq_curr;
952				else
953					ke->ke_runq = &KSEQ_SELF()->ksq_idle;
954			}
955			runq_add(ke->ke_runq, ke);
956			/* setrunqueue(td); */
957		}
958	} else {
959		if (ke->ke_runq)
960			kseq_rem(KSEQ_CPU(ke->ke_cpu), ke);
961		/*
962		 * We will not be on the run queue. So we must be
963		 * sleeping or similar.
964		 */
965		if (td->td_proc->p_flag & P_SA)
966			kse_reassign(ke);
967	}
968	newtd = choosethread();
969	if (td != newtd)
970		cpu_switch(td, newtd);
971	sched_lock.mtx_lock = (uintptr_t)td;
972
973	td->td_oncpu = PCPU_GET(cpuid);
974}
975
976void
977sched_nice(struct ksegrp *kg, int nice)
978{
979	struct kse *ke;
980	struct thread *td;
981	struct kseq *kseq;
982
983	PROC_LOCK_ASSERT(kg->kg_proc, MA_OWNED);
984	mtx_assert(&sched_lock, MA_OWNED);
985	/*
986	 * We need to adjust the nice counts for running KSEs.
987	 */
988	if (kg->kg_pri_class == PRI_TIMESHARE)
989		FOREACH_KSE_IN_GROUP(kg, ke) {
990			if (ke->ke_runq == NULL)
991				continue;
992			kseq = KSEQ_CPU(ke->ke_cpu);
993			kseq_nice_rem(kseq, kg->kg_nice);
994			kseq_nice_add(kseq, nice);
995		}
996	kg->kg_nice = nice;
997	sched_priority(kg);
998	FOREACH_THREAD_IN_GROUP(kg, td)
999		td->td_flags |= TDF_NEEDRESCHED;
1000}
1001
1002void
1003sched_sleep(struct thread *td, u_char prio)
1004{
1005	mtx_assert(&sched_lock, MA_OWNED);
1006
1007	td->td_slptime = ticks;
1008	td->td_priority = prio;
1009
1010	CTR2(KTR_ULE, "sleep kse %p (tick: %d)",
1011	    td->td_kse, td->td_slptime);
1012}
1013
1014void
1015sched_wakeup(struct thread *td)
1016{
1017	mtx_assert(&sched_lock, MA_OWNED);
1018
1019	/*
1020	 * Let the kseg know how long we slept for.  This is because process
1021	 * interactivity behavior is modeled in the kseg.
1022	 */
1023	if (td->td_slptime) {
1024		struct ksegrp *kg;
1025		int hzticks;
1026
1027		kg = td->td_ksegrp;
1028		hzticks = ticks - td->td_slptime;
1029		kg->kg_slptime += hzticks << 10;
1030		sched_interact_update(kg);
1031		sched_priority(kg);
1032		if (td->td_kse)
1033			sched_slice(td->td_kse);
1034		CTR2(KTR_ULE, "wakeup kse %p (%d ticks)",
1035		    td->td_kse, hzticks);
1036		td->td_slptime = 0;
1037	}
1038	setrunqueue(td);
1039}
1040
1041/*
1042 * Penalize the parent for creating a new child and initialize the child's
1043 * priority.
1044 */
1045void
1046sched_fork(struct proc *p, struct proc *p1)
1047{
1048
1049	mtx_assert(&sched_lock, MA_OWNED);
1050
1051	sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1));
1052	sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1));
1053	sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1));
1054}
1055
1056void
1057sched_fork_kse(struct kse *ke, struct kse *child)
1058{
1059
1060	child->ke_slice = 1;	/* Attempt to quickly learn interactivity. */
1061	child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */
1062	child->ke_runq = NULL;
1063
1064	/* Grab our parents cpu estimation information. */
1065	child->ke_ticks = ke->ke_ticks;
1066	child->ke_ltick = ke->ke_ltick;
1067	child->ke_ftick = ke->ke_ftick;
1068}
1069
1070void
1071sched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child)
1072{
1073
1074	PROC_LOCK_ASSERT(child->kg_proc, MA_OWNED);
1075	/* XXX Need something better here */
1076
1077	child->kg_slptime = kg->kg_slptime / SCHED_SLP_RUN_THROTTLE;
1078	child->kg_runtime = kg->kg_runtime / SCHED_SLP_RUN_THROTTLE;
1079	kg->kg_runtime += tickincr << 10;
1080	sched_interact_update(kg);
1081
1082	child->kg_user_pri = kg->kg_user_pri;
1083	child->kg_nice = kg->kg_nice;
1084}
1085
1086void
1087sched_fork_thread(struct thread *td, struct thread *child)
1088{
1089}
1090
1091void
1092sched_class(struct ksegrp *kg, int class)
1093{
1094	struct kseq *kseq;
1095	struct kse *ke;
1096
1097	mtx_assert(&sched_lock, MA_OWNED);
1098	if (kg->kg_pri_class == class)
1099		return;
1100
1101	FOREACH_KSE_IN_GROUP(kg, ke) {
1102		if (ke->ke_state != KES_ONRUNQ &&
1103		    ke->ke_state != KES_THREAD)
1104			continue;
1105		kseq = KSEQ_CPU(ke->ke_cpu);
1106
1107		kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--;
1108		kseq->ksq_loads[PRI_BASE(class)]++;
1109
1110		if (kg->kg_pri_class == PRI_TIMESHARE)
1111			kseq_nice_rem(kseq, kg->kg_nice);
1112		else if (class == PRI_TIMESHARE)
1113			kseq_nice_add(kseq, kg->kg_nice);
1114	}
1115
1116	kg->kg_pri_class = class;
1117}
1118
1119/*
1120 * Return some of the child's priority and interactivity to the parent.
1121 */
1122void
1123sched_exit(struct proc *p, struct proc *child)
1124{
1125	/* XXX Need something better here */
1126	mtx_assert(&sched_lock, MA_OWNED);
1127	sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child));
1128	sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(child));
1129}
1130
1131void
1132sched_exit_kse(struct kse *ke, struct kse *child)
1133{
1134	kseq_rem(KSEQ_CPU(child->ke_cpu), child);
1135}
1136
1137void
1138sched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child)
1139{
1140	/* kg->kg_slptime += child->kg_slptime; */
1141	kg->kg_runtime += child->kg_runtime;
1142	sched_interact_update(kg);
1143}
1144
1145void
1146sched_exit_thread(struct thread *td, struct thread *child)
1147{
1148}
1149
1150void
1151sched_clock(struct thread *td)
1152{
1153	struct kseq *kseq;
1154	struct ksegrp *kg;
1155	struct kse *ke;
1156
1157	/*
1158	 * sched_setup() apparently happens prior to stathz being set.  We
1159	 * need to resolve the timers earlier in the boot so we can avoid
1160	 * calculating this here.
1161	 */
1162	if (realstathz == 0) {
1163		realstathz = stathz ? stathz : hz;
1164		tickincr = hz / realstathz;
1165		/*
1166		 * XXX This does not work for values of stathz that are much
1167		 * larger than hz.
1168		 */
1169		if (tickincr == 0)
1170			tickincr = 1;
1171	}
1172
1173	ke = td->td_kse;
1174	kg = ke->ke_ksegrp;
1175
1176	mtx_assert(&sched_lock, MA_OWNED);
1177	KASSERT((td != NULL), ("schedclock: null thread pointer"));
1178
1179	/* Adjust ticks for pctcpu */
1180	ke->ke_ticks++;
1181	ke->ke_ltick = ticks;
1182
1183	/* Go up to one second beyond our max and then trim back down */
1184	if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick)
1185		sched_pctcpu_update(ke);
1186
1187	if (td->td_flags & TDF_IDLETD)
1188		return;
1189
1190	CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)",
1191	    ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10);
1192	/*
1193	 * We only do slicing code for TIMESHARE ksegrps.
1194	 */
1195	if (kg->kg_pri_class != PRI_TIMESHARE)
1196		return;
1197	/*
1198	 * We used a tick charge it to the ksegrp so that we can compute our
1199	 * interactivity.
1200	 */
1201	kg->kg_runtime += tickincr << 10;
1202	sched_interact_update(kg);
1203
1204	/*
1205	 * We used up one time slice.
1206	 */
1207	ke->ke_slice--;
1208	kseq = KSEQ_SELF();
1209#ifdef SMP
1210	kseq->ksq_rslices--;
1211#endif
1212
1213	if (ke->ke_slice > 0)
1214		return;
1215	/*
1216	 * We're out of time, recompute priorities and requeue.
1217	 */
1218	kseq_rem(kseq, ke);
1219	sched_priority(kg);
1220	sched_slice(ke);
1221	if (SCHED_CURR(kg, ke))
1222		ke->ke_runq = kseq->ksq_curr;
1223	else
1224		ke->ke_runq = kseq->ksq_next;
1225	kseq_add(kseq, ke);
1226	td->td_flags |= TDF_NEEDRESCHED;
1227}
1228
1229int
1230sched_runnable(void)
1231{
1232	struct kseq *kseq;
1233	int load;
1234
1235	load = 1;
1236
1237	mtx_lock_spin(&sched_lock);
1238	kseq = KSEQ_SELF();
1239#ifdef SMP
1240	if (kseq->ksq_assigned)
1241		kseq_assign(kseq);
1242#endif
1243	if ((curthread->td_flags & TDF_IDLETD) != 0) {
1244		if (kseq->ksq_load > 0)
1245			goto out;
1246	} else
1247		if (kseq->ksq_load - 1 > 0)
1248			goto out;
1249	load = 0;
1250out:
1251	mtx_unlock_spin(&sched_lock);
1252	return (load);
1253}
1254
1255void
1256sched_userret(struct thread *td)
1257{
1258	struct ksegrp *kg;
1259
1260	kg = td->td_ksegrp;
1261
1262	if (td->td_priority != kg->kg_user_pri) {
1263		mtx_lock_spin(&sched_lock);
1264		td->td_priority = kg->kg_user_pri;
1265		mtx_unlock_spin(&sched_lock);
1266	}
1267}
1268
1269struct kse *
1270sched_choose(void)
1271{
1272	struct kseq *kseq;
1273	struct kse *ke;
1274
1275	mtx_assert(&sched_lock, MA_OWNED);
1276	kseq = KSEQ_SELF();
1277#ifdef SMP
1278retry:
1279	if (kseq->ksq_assigned)
1280		kseq_assign(kseq);
1281#endif
1282	ke = kseq_choose(kseq);
1283	if (ke) {
1284#ifdef SMP
1285		if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE)
1286			if (kseq_find())
1287				goto retry;
1288#endif
1289		runq_remove(ke->ke_runq, ke);
1290		ke->ke_state = KES_THREAD;
1291
1292		if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) {
1293			CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)",
1294			    ke, ke->ke_runq, ke->ke_slice,
1295			    ke->ke_thread->td_priority);
1296		}
1297		return (ke);
1298	}
1299#ifdef SMP
1300	if (kseq_find())
1301		goto retry;
1302#endif
1303
1304	return (NULL);
1305}
1306
1307void
1308sched_add(struct thread *td)
1309{
1310	struct kseq *kseq;
1311	struct ksegrp *kg;
1312	struct kse *ke;
1313	int class;
1314
1315	mtx_assert(&sched_lock, MA_OWNED);
1316	ke = td->td_kse;
1317	kg = td->td_ksegrp;
1318	if (ke->ke_flags & KEF_ASSIGNED)
1319		return;
1320	kseq = KSEQ_SELF();
1321	KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE"));
1322	KASSERT((ke->ke_thread->td_kse != NULL),
1323	    ("sched_add: No KSE on thread"));
1324	KASSERT(ke->ke_state != KES_ONRUNQ,
1325	    ("sched_add: kse %p (%s) already in run queue", ke,
1326	    ke->ke_proc->p_comm));
1327	KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
1328	    ("sched_add: process swapped out"));
1329	KASSERT(ke->ke_runq == NULL,
1330	    ("sched_add: KSE %p is still assigned to a run queue", ke));
1331
1332	class = PRI_BASE(kg->kg_pri_class);
1333	switch (class) {
1334	case PRI_ITHD:
1335	case PRI_REALTIME:
1336		ke->ke_runq = kseq->ksq_curr;
1337		ke->ke_slice = SCHED_SLICE_MAX;
1338		ke->ke_cpu = PCPU_GET(cpuid);
1339		break;
1340	case PRI_TIMESHARE:
1341#ifdef SMP
1342		if (ke->ke_cpu != PCPU_GET(cpuid)) {
1343			kseq_notify(ke, ke->ke_cpu);
1344			return;
1345		}
1346#endif
1347		if (SCHED_CURR(kg, ke))
1348			ke->ke_runq = kseq->ksq_curr;
1349		else
1350			ke->ke_runq = kseq->ksq_next;
1351		break;
1352	case PRI_IDLE:
1353#ifdef SMP
1354		if (ke->ke_cpu != PCPU_GET(cpuid)) {
1355			kseq_notify(ke, ke->ke_cpu);
1356			return;
1357		}
1358#endif
1359		/*
1360		 * This is for priority prop.
1361		 */
1362		if (ke->ke_thread->td_priority < PRI_MIN_IDLE)
1363			ke->ke_runq = kseq->ksq_curr;
1364		else
1365			ke->ke_runq = &kseq->ksq_idle;
1366		ke->ke_slice = SCHED_SLICE_MIN;
1367		break;
1368	default:
1369		panic("Unknown pri class.\n");
1370		break;
1371	}
1372#ifdef SMP
1373	/*
1374	 * If there are any idle processors, give them our extra load.
1375	 */
1376	if (kseq_idle && class != PRI_ITHD &&
1377	    (kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] +
1378	    kseq->ksq_loads[PRI_REALTIME]) >= kseq->ksq_cpus) {
1379		int cpu;
1380
1381		/*
1382		 * Multiple cpus could find this bit simultaneously but the
1383		 * race shouldn't be terrible.
1384		 */
1385		cpu = ffs(kseq_idle);
1386		if (cpu) {
1387			cpu--;
1388			atomic_clear_int(&kseq_idle, 1 << cpu);
1389			ke->ke_cpu = cpu;
1390			ke->ke_runq = NULL;
1391			kseq_notify(ke, cpu);
1392			return;
1393		}
1394	}
1395	if (class == PRI_TIMESHARE || class == PRI_REALTIME)
1396		atomic_clear_int(&kseq_idle, PCPU_GET(cpumask));
1397#endif
1398        if (td->td_priority < curthread->td_priority)
1399                curthread->td_flags |= TDF_NEEDRESCHED;
1400
1401	ke->ke_ksegrp->kg_runq_kses++;
1402	ke->ke_state = KES_ONRUNQ;
1403
1404	runq_add(ke->ke_runq, ke);
1405	kseq_add(kseq, ke);
1406}
1407
1408void
1409sched_rem(struct thread *td)
1410{
1411	struct kseq *kseq;
1412	struct kse *ke;
1413
1414	ke = td->td_kse;
1415	/*
1416	 * It is safe to just return here because sched_rem() is only ever
1417	 * used in places where we're immediately going to add the
1418	 * kse back on again.  In that case it'll be added with the correct
1419	 * thread and priority when the caller drops the sched_lock.
1420	 */
1421	if (ke->ke_flags & KEF_ASSIGNED)
1422		return;
1423	mtx_assert(&sched_lock, MA_OWNED);
1424	KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue"));
1425
1426	ke->ke_state = KES_THREAD;
1427	ke->ke_ksegrp->kg_runq_kses--;
1428	kseq = KSEQ_CPU(ke->ke_cpu);
1429	runq_remove(ke->ke_runq, ke);
1430	kseq_rem(kseq, ke);
1431}
1432
1433fixpt_t
1434sched_pctcpu(struct thread *td)
1435{
1436	fixpt_t pctcpu;
1437	struct kse *ke;
1438
1439	pctcpu = 0;
1440	ke = td->td_kse;
1441	if (ke == NULL)
1442		return (0);
1443
1444	mtx_lock_spin(&sched_lock);
1445	if (ke->ke_ticks) {
1446		int rtick;
1447
1448		/*
1449		 * Don't update more frequently than twice a second.  Allowing
1450		 * this causes the cpu usage to decay away too quickly due to
1451		 * rounding errors.
1452		 */
1453		if (ke->ke_ltick < (ticks - (hz / 2)))
1454			sched_pctcpu_update(ke);
1455		/* How many rtick per second ? */
1456		rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS);
1457		pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT;
1458	}
1459
1460	ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick;
1461	mtx_unlock_spin(&sched_lock);
1462
1463	return (pctcpu);
1464}
1465
1466int
1467sched_sizeof_kse(void)
1468{
1469	return (sizeof(struct kse) + sizeof(struct ke_sched));
1470}
1471
1472int
1473sched_sizeof_ksegrp(void)
1474{
1475	return (sizeof(struct ksegrp) + sizeof(struct kg_sched));
1476}
1477
1478int
1479sched_sizeof_proc(void)
1480{
1481	return (sizeof(struct proc));
1482}
1483
1484int
1485sched_sizeof_thread(void)
1486{
1487	return (sizeof(struct thread) + sizeof(struct td_sched));
1488}
1489