xref: /titanic_44/usr/src/uts/common/disp/disp.c (revision b0fe7b8fa79924061f3bdf7f240ea116c2c0b704)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
27 /*	  All Rights Reserved  	*/
28 
29 
30 #pragma ident	"%Z%%M%	%I%	%E% SMI"	/* from SVr4.0 1.30 */
31 
32 #include <sys/types.h>
33 #include <sys/param.h>
34 #include <sys/sysmacros.h>
35 #include <sys/signal.h>
36 #include <sys/user.h>
37 #include <sys/systm.h>
38 #include <sys/sysinfo.h>
39 #include <sys/var.h>
40 #include <sys/errno.h>
41 #include <sys/cmn_err.h>
42 #include <sys/debug.h>
43 #include <sys/inline.h>
44 #include <sys/disp.h>
45 #include <sys/class.h>
46 #include <sys/bitmap.h>
47 #include <sys/kmem.h>
48 #include <sys/cpuvar.h>
49 #include <sys/vtrace.h>
50 #include <sys/tnf.h>
51 #include <sys/cpupart.h>
52 #include <sys/lgrp.h>
53 #include <sys/pg.h>
54 #include <sys/cmt.h>
55 #include <sys/bitset.h>
56 #include <sys/schedctl.h>
57 #include <sys/atomic.h>
58 #include <sys/dtrace.h>
59 #include <sys/sdt.h>
60 
61 #include <vm/as.h>
62 
63 #define	BOUND_CPU	0x1
64 #define	BOUND_PARTITION	0x2
65 #define	BOUND_INTR	0x4
66 
67 /* Dispatch queue allocation structure and functions */
68 struct disp_queue_info {
69 	disp_t	*dp;
70 	dispq_t *olddispq;
71 	dispq_t *newdispq;
72 	ulong_t	*olddqactmap;
73 	ulong_t	*newdqactmap;
74 	int	oldnglobpris;
75 };
76 static void	disp_dq_alloc(struct disp_queue_info *dptr, int numpris,
77     disp_t *dp);
78 static void	disp_dq_assign(struct disp_queue_info *dptr, int numpris);
79 static void	disp_dq_free(struct disp_queue_info *dptr);
80 
81 /* platform-specific routine to call when processor is idle */
82 static void	generic_idle_cpu();
83 void		(*idle_cpu)() = generic_idle_cpu;
84 
85 /* routines invoked when a CPU enters/exits the idle loop */
86 static void	idle_enter();
87 static void	idle_exit();
88 
89 /* platform-specific routine to call when thread is enqueued */
90 static void	generic_enq_thread(cpu_t *, int);
91 void		(*disp_enq_thread)(cpu_t *, int) = generic_enq_thread;
92 
93 pri_t	kpreemptpri;		/* priority where kernel preemption applies */
94 pri_t	upreemptpri = 0; 	/* priority where normal preemption applies */
95 pri_t	intr_pri;		/* interrupt thread priority base level */
96 
97 #define	KPQPRI	-1 		/* pri where cpu affinity is dropped for kpq */
98 pri_t	kpqpri = KPQPRI; 	/* can be set in /etc/system */
99 disp_t	cpu0_disp;		/* boot CPU's dispatch queue */
100 disp_lock_t	swapped_lock;	/* lock swapped threads and swap queue */
101 int	nswapped;		/* total number of swapped threads */
102 void	disp_swapped_enq(kthread_t *tp);
103 static void	disp_swapped_setrun(kthread_t *tp);
104 static void	cpu_resched(cpu_t *cp, pri_t tpri);
105 
106 /*
107  * If this is set, only interrupt threads will cause kernel preemptions.
108  * This is done by changing the value of kpreemptpri.  kpreemptpri
109  * will either be the max sysclass pri + 1 or the min interrupt pri.
110  */
111 int	only_intr_kpreempt;
112 
113 extern void set_idle_cpu(int cpun);
114 extern void unset_idle_cpu(int cpun);
115 static void setkpdq(kthread_t *tp, int borf);
116 #define	SETKP_BACK	0
117 #define	SETKP_FRONT	1
118 /*
119  * Parameter that determines how recently a thread must have run
120  * on the CPU to be considered loosely-bound to that CPU to reduce
121  * cold cache effects.  The interval is in hertz.
122  */
123 #define	RECHOOSE_INTERVAL 3
124 int	rechoose_interval = RECHOOSE_INTERVAL;
125 static cpu_t	*cpu_choose(kthread_t *, pri_t);
126 
127 /*
128  * Parameter that determines how long (in nanoseconds) a thread must
129  * be sitting on a run queue before it can be stolen by another CPU
130  * to reduce migrations.  The interval is in nanoseconds.
131  *
132  * The nosteal_nsec should be set by a platform code to an appropriate value.
133  * Setting it to 0 effectively disables the nosteal 'protection'
134  */
135 hrtime_t nosteal_nsec = -1;
136 
137 id_t	defaultcid;	/* system "default" class; see dispadmin(1M) */
138 
139 disp_lock_t	transition_lock;	/* lock on transitioning threads */
140 disp_lock_t	stop_lock;		/* lock on stopped threads */
141 
142 static void	cpu_dispqalloc(int numpris);
143 
144 /*
145  * This gets returned by disp_getwork/disp_getbest if we couldn't steal
146  * a thread because it was sitting on its run queue for a very short
147  * period of time.
148  */
149 #define	T_DONTSTEAL	(kthread_t *)(-1) /* returned by disp_getwork/getbest */
150 
151 static kthread_t	*disp_getwork(cpu_t *to);
152 static kthread_t	*disp_getbest(disp_t *from);
153 static kthread_t	*disp_ratify(kthread_t *tp, disp_t *kpq);
154 
155 void	swtch_to(kthread_t *);
156 
157 /*
158  * dispatcher and scheduler initialization
159  */
160 
161 /*
162  * disp_setup - Common code to calculate and allocate dispatcher
163  *		variables and structures based on the maximum priority.
164  */
165 static void
166 disp_setup(pri_t maxglobpri, pri_t oldnglobpris)
167 {
168 	pri_t	newnglobpris;
169 
170 	ASSERT(MUTEX_HELD(&cpu_lock));
171 
172 	newnglobpris = maxglobpri + 1 + LOCK_LEVEL;
173 
174 	if (newnglobpris > oldnglobpris) {
175 		/*
176 		 * Allocate new kp queues for each CPU partition.
177 		 */
178 		cpupart_kpqalloc(newnglobpris);
179 
180 		/*
181 		 * Allocate new dispatch queues for each CPU.
182 		 */
183 		cpu_dispqalloc(newnglobpris);
184 
185 		/*
186 		 * compute new interrupt thread base priority
187 		 */
188 		intr_pri = maxglobpri;
189 		if (only_intr_kpreempt) {
190 			kpreemptpri = intr_pri + 1;
191 			if (kpqpri == KPQPRI)
192 				kpqpri = kpreemptpri;
193 		}
194 		v.v_nglobpris = newnglobpris;
195 	}
196 }
197 
198 /*
199  * dispinit - Called to initialize all loaded classes and the
200  *	      dispatcher framework.
201  */
202 void
203 dispinit(void)
204 {
205 	id_t	cid;
206 	pri_t	maxglobpri;
207 	pri_t	cl_maxglobpri;
208 
209 	maxglobpri = -1;
210 
211 	/*
212 	 * Initialize transition lock, which will always be set.
213 	 */
214 	DISP_LOCK_INIT(&transition_lock);
215 	disp_lock_enter_high(&transition_lock);
216 	DISP_LOCK_INIT(&stop_lock);
217 
218 	mutex_enter(&cpu_lock);
219 	CPU->cpu_disp->disp_maxrunpri = -1;
220 	CPU->cpu_disp->disp_max_unbound_pri = -1;
221 
222 	/*
223 	 * Initialize the default CPU partition.
224 	 */
225 	cpupart_initialize_default();
226 	/*
227 	 * Call the class specific initialization functions for
228 	 * all pre-installed schedulers.
229 	 *
230 	 * We pass the size of a class specific parameter
231 	 * buffer to each of the initialization functions
232 	 * to try to catch problems with backward compatibility
233 	 * of class modules.
234 	 *
235 	 * For example a new class module running on an old system
236 	 * which didn't provide sufficiently large parameter buffers
237 	 * would be bad news. Class initialization modules can check for
238 	 * this and take action if they detect a problem.
239 	 */
240 
241 	for (cid = 0; cid < nclass; cid++) {
242 		sclass_t	*sc;
243 
244 		sc = &sclass[cid];
245 		if (SCHED_INSTALLED(sc)) {
246 			cl_maxglobpri = sc->cl_init(cid, PC_CLPARMSZ,
247 			    &sc->cl_funcs);
248 			if (cl_maxglobpri > maxglobpri)
249 				maxglobpri = cl_maxglobpri;
250 		}
251 	}
252 	kpreemptpri = (pri_t)v.v_maxsyspri + 1;
253 	if (kpqpri == KPQPRI)
254 		kpqpri = kpreemptpri;
255 
256 	ASSERT(maxglobpri >= 0);
257 	disp_setup(maxglobpri, 0);
258 
259 	mutex_exit(&cpu_lock);
260 
261 	/*
262 	 * Get the default class ID; this may be later modified via
263 	 * dispadmin(1M).  This will load the class (normally TS) and that will
264 	 * call disp_add(), which is why we had to drop cpu_lock first.
265 	 */
266 	if (getcid(defaultclass, &defaultcid) != 0) {
267 		cmn_err(CE_PANIC, "Couldn't load default scheduling class '%s'",
268 		    defaultclass);
269 	}
270 }
271 
272 /*
273  * disp_add - Called with class pointer to initialize the dispatcher
274  *	      for a newly loaded class.
275  */
276 void
277 disp_add(sclass_t *clp)
278 {
279 	pri_t	maxglobpri;
280 	pri_t	cl_maxglobpri;
281 
282 	mutex_enter(&cpu_lock);
283 	/*
284 	 * Initialize the scheduler class.
285 	 */
286 	maxglobpri = (pri_t)(v.v_nglobpris - LOCK_LEVEL - 1);
287 	cl_maxglobpri = clp->cl_init(clp - sclass, PC_CLPARMSZ, &clp->cl_funcs);
288 	if (cl_maxglobpri > maxglobpri)
289 		maxglobpri = cl_maxglobpri;
290 
291 	/*
292 	 * Save old queue information.  Since we're initializing a
293 	 * new scheduling class which has just been loaded, then
294 	 * the size of the dispq may have changed.  We need to handle
295 	 * that here.
296 	 */
297 	disp_setup(maxglobpri, v.v_nglobpris);
298 
299 	mutex_exit(&cpu_lock);
300 }
301 
302 
303 /*
304  * For each CPU, allocate new dispatch queues
305  * with the stated number of priorities.
306  */
307 static void
308 cpu_dispqalloc(int numpris)
309 {
310 	cpu_t	*cpup;
311 	struct disp_queue_info	*disp_mem;
312 	int i, num;
313 
314 	ASSERT(MUTEX_HELD(&cpu_lock));
315 
316 	disp_mem = kmem_zalloc(NCPU *
317 	    sizeof (struct disp_queue_info), KM_SLEEP);
318 
319 	/*
320 	 * This routine must allocate all of the memory before stopping
321 	 * the cpus because it must not sleep in kmem_alloc while the
322 	 * CPUs are stopped.  Locks they hold will not be freed until they
323 	 * are restarted.
324 	 */
325 	i = 0;
326 	cpup = cpu_list;
327 	do {
328 		disp_dq_alloc(&disp_mem[i], numpris, cpup->cpu_disp);
329 		i++;
330 		cpup = cpup->cpu_next;
331 	} while (cpup != cpu_list);
332 	num = i;
333 
334 	pause_cpus(NULL);
335 	for (i = 0; i < num; i++)
336 		disp_dq_assign(&disp_mem[i], numpris);
337 	start_cpus();
338 
339 	/*
340 	 * I must free all of the memory after starting the cpus because
341 	 * I can not risk sleeping in kmem_free while the cpus are stopped.
342 	 */
343 	for (i = 0; i < num; i++)
344 		disp_dq_free(&disp_mem[i]);
345 
346 	kmem_free(disp_mem, NCPU * sizeof (struct disp_queue_info));
347 }
348 
349 static void
350 disp_dq_alloc(struct disp_queue_info *dptr, int numpris, disp_t	*dp)
351 {
352 	dptr->newdispq = kmem_zalloc(numpris * sizeof (dispq_t), KM_SLEEP);
353 	dptr->newdqactmap = kmem_zalloc(((numpris / BT_NBIPUL) + 1) *
354 	    sizeof (long), KM_SLEEP);
355 	dptr->dp = dp;
356 }
357 
358 static void
359 disp_dq_assign(struct disp_queue_info *dptr, int numpris)
360 {
361 	disp_t	*dp;
362 
363 	dp = dptr->dp;
364 	dptr->olddispq = dp->disp_q;
365 	dptr->olddqactmap = dp->disp_qactmap;
366 	dptr->oldnglobpris = dp->disp_npri;
367 
368 	ASSERT(dptr->oldnglobpris < numpris);
369 
370 	if (dptr->olddispq != NULL) {
371 		/*
372 		 * Use kcopy because bcopy is platform-specific
373 		 * and could block while we might have paused the cpus.
374 		 */
375 		(void) kcopy(dptr->olddispq, dptr->newdispq,
376 		    dptr->oldnglobpris * sizeof (dispq_t));
377 		(void) kcopy(dptr->olddqactmap, dptr->newdqactmap,
378 		    ((dptr->oldnglobpris / BT_NBIPUL) + 1) *
379 		    sizeof (long));
380 	}
381 	dp->disp_q = dptr->newdispq;
382 	dp->disp_qactmap = dptr->newdqactmap;
383 	dp->disp_q_limit = &dptr->newdispq[numpris];
384 	dp->disp_npri = numpris;
385 }
386 
387 static void
388 disp_dq_free(struct disp_queue_info *dptr)
389 {
390 	if (dptr->olddispq != NULL)
391 		kmem_free(dptr->olddispq,
392 		    dptr->oldnglobpris * sizeof (dispq_t));
393 	if (dptr->olddqactmap != NULL)
394 		kmem_free(dptr->olddqactmap,
395 		    ((dptr->oldnglobpris / BT_NBIPUL) + 1) * sizeof (long));
396 }
397 
398 /*
399  * For a newly created CPU, initialize the dispatch queue.
400  * This is called before the CPU is known through cpu[] or on any lists.
401  */
402 void
403 disp_cpu_init(cpu_t *cp)
404 {
405 	disp_t	*dp;
406 	dispq_t	*newdispq;
407 	ulong_t	*newdqactmap;
408 
409 	ASSERT(MUTEX_HELD(&cpu_lock));	/* protect dispatcher queue sizes */
410 
411 	if (cp == cpu0_disp.disp_cpu)
412 		dp = &cpu0_disp;
413 	else
414 		dp = kmem_alloc(sizeof (disp_t), KM_SLEEP);
415 	bzero(dp, sizeof (disp_t));
416 	cp->cpu_disp = dp;
417 	dp->disp_cpu = cp;
418 	dp->disp_maxrunpri = -1;
419 	dp->disp_max_unbound_pri = -1;
420 	DISP_LOCK_INIT(&cp->cpu_thread_lock);
421 	/*
422 	 * Allocate memory for the dispatcher queue headers
423 	 * and the active queue bitmap.
424 	 */
425 	newdispq = kmem_zalloc(v.v_nglobpris * sizeof (dispq_t), KM_SLEEP);
426 	newdqactmap = kmem_zalloc(((v.v_nglobpris / BT_NBIPUL) + 1) *
427 	    sizeof (long), KM_SLEEP);
428 	dp->disp_q = newdispq;
429 	dp->disp_qactmap = newdqactmap;
430 	dp->disp_q_limit = &newdispq[v.v_nglobpris];
431 	dp->disp_npri = v.v_nglobpris;
432 }
433 
434 void
435 disp_cpu_fini(cpu_t *cp)
436 {
437 	ASSERT(MUTEX_HELD(&cpu_lock));
438 
439 	disp_kp_free(cp->cpu_disp);
440 	if (cp->cpu_disp != &cpu0_disp)
441 		kmem_free(cp->cpu_disp, sizeof (disp_t));
442 }
443 
444 /*
445  * Allocate new, larger kpreempt dispatch queue to replace the old one.
446  */
447 void
448 disp_kp_alloc(disp_t *dq, pri_t npri)
449 {
450 	struct disp_queue_info	mem_info;
451 
452 	if (npri > dq->disp_npri) {
453 		/*
454 		 * Allocate memory for the new array.
455 		 */
456 		disp_dq_alloc(&mem_info, npri, dq);
457 
458 		/*
459 		 * We need to copy the old structures to the new
460 		 * and free the old.
461 		 */
462 		disp_dq_assign(&mem_info, npri);
463 		disp_dq_free(&mem_info);
464 	}
465 }
466 
467 /*
468  * Free dispatch queue.
469  * Used for the kpreempt queues for a removed CPU partition and
470  * for the per-CPU queues of deleted CPUs.
471  */
472 void
473 disp_kp_free(disp_t *dq)
474 {
475 	struct disp_queue_info	mem_info;
476 
477 	mem_info.olddispq = dq->disp_q;
478 	mem_info.olddqactmap = dq->disp_qactmap;
479 	mem_info.oldnglobpris = dq->disp_npri;
480 	disp_dq_free(&mem_info);
481 }
482 
483 /*
484  * End dispatcher and scheduler initialization.
485  */
486 
487 /*
488  * See if there's anything to do other than remain idle.
489  * Return non-zero if there is.
490  *
491  * This function must be called with high spl, or with
492  * kernel preemption disabled to prevent the partition's
493  * active cpu list from changing while being traversed.
494  *
495  */
496 int
497 disp_anywork(void)
498 {
499 	cpu_t   *cp = CPU;
500 	cpu_t   *ocp;
501 
502 	if (cp->cpu_disp->disp_nrunnable != 0)
503 		return (1);
504 
505 	if (!(cp->cpu_flags & CPU_OFFLINE)) {
506 		if (CP_MAXRUNPRI(cp->cpu_part) >= 0)
507 			return (1);
508 
509 		/*
510 		 * Work can be taken from another CPU if:
511 		 *	- There is unbound work on the run queue
512 		 *	- That work isn't a thread undergoing a
513 		 *	- context switch on an otherwise empty queue.
514 		 *	- The CPU isn't running the idle loop.
515 		 */
516 		for (ocp = cp->cpu_next_part; ocp != cp;
517 		    ocp = ocp->cpu_next_part) {
518 			ASSERT(CPU_ACTIVE(ocp));
519 
520 			if (ocp->cpu_disp->disp_max_unbound_pri != -1 &&
521 			    !((ocp->cpu_disp_flags & CPU_DISP_DONTSTEAL) &&
522 			    ocp->cpu_disp->disp_nrunnable == 1) &&
523 			    ocp->cpu_dispatch_pri != -1)
524 				return (1);
525 		}
526 	}
527 	return (0);
528 }
529 
530 /*
531  * Called when CPU enters the idle loop
532  */
533 static void
534 idle_enter()
535 {
536 	cpu_t		*cp = CPU;
537 
538 	new_cpu_mstate(CMS_IDLE, gethrtime_unscaled());
539 	CPU_STATS_ADDQ(cp, sys, idlethread, 1);
540 	set_idle_cpu(cp->cpu_id);	/* arch-dependent hook */
541 }
542 
543 /*
544  * Called when CPU exits the idle loop
545  */
546 static void
547 idle_exit()
548 {
549 	cpu_t		*cp = CPU;
550 
551 	new_cpu_mstate(CMS_SYSTEM, gethrtime_unscaled());
552 	unset_idle_cpu(cp->cpu_id);	/* arch-dependent hook */
553 }
554 
555 /*
556  * Idle loop.
557  */
558 void
559 idle()
560 {
561 	struct cpu	*cp = CPU;		/* pointer to this CPU */
562 	kthread_t	*t;			/* taken thread */
563 
564 	idle_enter();
565 
566 	/*
567 	 * Uniprocessor version of idle loop.
568 	 * Do this until notified that we're on an actual multiprocessor.
569 	 */
570 	while (ncpus == 1) {
571 		if (cp->cpu_disp->disp_nrunnable == 0) {
572 			(*idle_cpu)();
573 			continue;
574 		}
575 		idle_exit();
576 		swtch();
577 
578 		idle_enter(); /* returned from swtch */
579 	}
580 
581 	/*
582 	 * Multiprocessor idle loop.
583 	 */
584 	for (;;) {
585 		/*
586 		 * If CPU is completely quiesced by p_online(2), just wait
587 		 * here with minimal bus traffic until put online.
588 		 */
589 		while (cp->cpu_flags & CPU_QUIESCED)
590 			(*idle_cpu)();
591 
592 		if (cp->cpu_disp->disp_nrunnable != 0) {
593 			idle_exit();
594 			swtch();
595 		} else {
596 			if (cp->cpu_flags & CPU_OFFLINE)
597 				continue;
598 			if ((t = disp_getwork(cp)) == NULL) {
599 				if (cp->cpu_chosen_level != -1) {
600 					disp_t *dp = cp->cpu_disp;
601 					disp_t *kpq;
602 
603 					disp_lock_enter(&dp->disp_lock);
604 					/*
605 					 * Set kpq under lock to prevent
606 					 * migration between partitions.
607 					 */
608 					kpq = &cp->cpu_part->cp_kp_queue;
609 					if (kpq->disp_maxrunpri == -1)
610 						cp->cpu_chosen_level = -1;
611 					disp_lock_exit(&dp->disp_lock);
612 				}
613 				(*idle_cpu)();
614 				continue;
615 			}
616 			/*
617 			 * If there was a thread but we couldn't steal
618 			 * it, then keep trying.
619 			 */
620 			if (t == T_DONTSTEAL)
621 				continue;
622 			idle_exit();
623 			swtch_to(t);
624 		}
625 		idle_enter(); /* returned from swtch/swtch_to */
626 	}
627 }
628 
629 
630 /*
631  * Preempt the currently running thread in favor of the highest
632  * priority thread.  The class of the current thread controls
633  * where it goes on the dispatcher queues. If panicking, turn
634  * preemption off.
635  */
636 void
637 preempt()
638 {
639 	kthread_t 	*t = curthread;
640 	klwp_t 		*lwp = ttolwp(curthread);
641 
642 	if (panicstr)
643 		return;
644 
645 	TRACE_0(TR_FAC_DISP, TR_PREEMPT_START, "preempt_start");
646 
647 	thread_lock(t);
648 
649 	if (t->t_state != TS_ONPROC || t->t_disp_queue != CPU->cpu_disp) {
650 		/*
651 		 * this thread has already been chosen to be run on
652 		 * another CPU. Clear kprunrun on this CPU since we're
653 		 * already headed for swtch().
654 		 */
655 		CPU->cpu_kprunrun = 0;
656 		thread_unlock_nopreempt(t);
657 		TRACE_0(TR_FAC_DISP, TR_PREEMPT_END, "preempt_end");
658 	} else {
659 		if (lwp != NULL)
660 			lwp->lwp_ru.nivcsw++;
661 		CPU_STATS_ADDQ(CPU, sys, inv_swtch, 1);
662 		THREAD_TRANSITION(t);
663 		CL_PREEMPT(t);
664 		DTRACE_SCHED(preempt);
665 		thread_unlock_nopreempt(t);
666 
667 		TRACE_0(TR_FAC_DISP, TR_PREEMPT_END, "preempt_end");
668 
669 		swtch();		/* clears CPU->cpu_runrun via disp() */
670 	}
671 }
672 
673 extern kthread_t *thread_unpin();
674 
675 /*
676  * disp() - find the highest priority thread for this processor to run, and
677  * set it in TS_ONPROC state so that resume() can be called to run it.
678  */
679 static kthread_t *
680 disp()
681 {
682 	cpu_t		*cpup;
683 	disp_t		*dp;
684 	kthread_t	*tp;
685 	dispq_t		*dq;
686 	int		maxrunword;
687 	pri_t		pri;
688 	disp_t		*kpq;
689 
690 	TRACE_0(TR_FAC_DISP, TR_DISP_START, "disp_start");
691 
692 	cpup = CPU;
693 	/*
694 	 * Find the highest priority loaded, runnable thread.
695 	 */
696 	dp = cpup->cpu_disp;
697 
698 reschedule:
699 	/*
700 	 * If there is more important work on the global queue with a better
701 	 * priority than the maximum on this CPU, take it now.
702 	 */
703 	kpq = &cpup->cpu_part->cp_kp_queue;
704 	while ((pri = kpq->disp_maxrunpri) >= 0 &&
705 	    pri >= dp->disp_maxrunpri &&
706 	    (cpup->cpu_flags & CPU_OFFLINE) == 0 &&
707 	    (tp = disp_getbest(kpq)) != NULL) {
708 		if (disp_ratify(tp, kpq) != NULL) {
709 			TRACE_1(TR_FAC_DISP, TR_DISP_END,
710 			    "disp_end:tid %p", tp);
711 			return (tp);
712 		}
713 	}
714 
715 	disp_lock_enter(&dp->disp_lock);
716 	pri = dp->disp_maxrunpri;
717 
718 	/*
719 	 * If there is nothing to run, look at what's runnable on other queues.
720 	 * Choose the idle thread if the CPU is quiesced.
721 	 * Note that CPUs that have the CPU_OFFLINE flag set can still run
722 	 * interrupt threads, which will be the only threads on the CPU's own
723 	 * queue, but cannot run threads from other queues.
724 	 */
725 	if (pri == -1) {
726 		if (!(cpup->cpu_flags & CPU_OFFLINE)) {
727 			disp_lock_exit(&dp->disp_lock);
728 			if ((tp = disp_getwork(cpup)) == NULL ||
729 			    tp == T_DONTSTEAL) {
730 				tp = cpup->cpu_idle_thread;
731 				(void) splhigh();
732 				THREAD_ONPROC(tp, cpup);
733 				cpup->cpu_dispthread = tp;
734 				cpup->cpu_dispatch_pri = -1;
735 				cpup->cpu_runrun = cpup->cpu_kprunrun = 0;
736 				cpup->cpu_chosen_level = -1;
737 			}
738 		} else {
739 			disp_lock_exit_high(&dp->disp_lock);
740 			tp = cpup->cpu_idle_thread;
741 			THREAD_ONPROC(tp, cpup);
742 			cpup->cpu_dispthread = tp;
743 			cpup->cpu_dispatch_pri = -1;
744 			cpup->cpu_runrun = cpup->cpu_kprunrun = 0;
745 			cpup->cpu_chosen_level = -1;
746 		}
747 		TRACE_1(TR_FAC_DISP, TR_DISP_END,
748 			"disp_end:tid %p", tp);
749 		return (tp);
750 	}
751 
752 	dq = &dp->disp_q[pri];
753 	tp = dq->dq_first;
754 
755 	ASSERT(tp != NULL);
756 	ASSERT(tp->t_schedflag & TS_LOAD);	/* thread must be swapped in */
757 
758 	DTRACE_SCHED2(dequeue, kthread_t *, tp, disp_t *, dp);
759 
760 	/*
761 	 * Found it so remove it from queue.
762 	 */
763 	dp->disp_nrunnable--;
764 	dq->dq_sruncnt--;
765 	if ((dq->dq_first = tp->t_link) == NULL) {
766 		ulong_t	*dqactmap = dp->disp_qactmap;
767 
768 		ASSERT(dq->dq_sruncnt == 0);
769 		dq->dq_last = NULL;
770 
771 		/*
772 		 * The queue is empty, so the corresponding bit needs to be
773 		 * turned off in dqactmap.   If nrunnable != 0 just took the
774 		 * last runnable thread off the
775 		 * highest queue, so recompute disp_maxrunpri.
776 		 */
777 		maxrunword = pri >> BT_ULSHIFT;
778 		dqactmap[maxrunword] &= ~BT_BIW(pri);
779 
780 		if (dp->disp_nrunnable == 0) {
781 			dp->disp_max_unbound_pri = -1;
782 			dp->disp_maxrunpri = -1;
783 		} else {
784 			int ipri;
785 
786 			ipri = bt_gethighbit(dqactmap, maxrunword);
787 			dp->disp_maxrunpri = ipri;
788 			if (ipri < dp->disp_max_unbound_pri)
789 				dp->disp_max_unbound_pri = ipri;
790 		}
791 	} else {
792 		tp->t_link = NULL;
793 	}
794 
795 	/*
796 	 * Set TS_DONT_SWAP flag to prevent another processor from swapping
797 	 * out this thread before we have a chance to run it.
798 	 * While running, it is protected against swapping by t_lock.
799 	 */
800 	tp->t_schedflag |= TS_DONT_SWAP;
801 	cpup->cpu_dispthread = tp;		/* protected by spl only */
802 	cpup->cpu_dispatch_pri = pri;
803 	ASSERT(pri == DISP_PRIO(tp));
804 	thread_onproc(tp, cpup);  		/* set t_state to TS_ONPROC */
805 	disp_lock_exit_high(&dp->disp_lock);	/* drop run queue lock */
806 
807 	ASSERT(tp != NULL);
808 	TRACE_1(TR_FAC_DISP, TR_DISP_END,
809 		"disp_end:tid %p", tp);
810 
811 	if (disp_ratify(tp, kpq) == NULL)
812 		goto reschedule;
813 
814 	return (tp);
815 }
816 
817 /*
818  * swtch()
819  *	Find best runnable thread and run it.
820  *	Called with the current thread already switched to a new state,
821  *	on a sleep queue, run queue, stopped, and not zombied.
822  *	May be called at any spl level less than or equal to LOCK_LEVEL.
823  *	Always drops spl to the base level (spl0()).
824  */
825 void
826 swtch()
827 {
828 	kthread_t	*t = curthread;
829 	kthread_t	*next;
830 	cpu_t		*cp;
831 
832 	TRACE_0(TR_FAC_DISP, TR_SWTCH_START, "swtch_start");
833 
834 	if (t->t_flag & T_INTR_THREAD)
835 		cpu_intr_swtch_enter(t);
836 
837 	if (t->t_intr != NULL) {
838 		/*
839 		 * We are an interrupt thread.  Setup and return
840 		 * the interrupted thread to be resumed.
841 		 */
842 		(void) splhigh();	/* block other scheduler action */
843 		cp = CPU;		/* now protected against migration */
844 		ASSERT(CPU_ON_INTR(cp) == 0);	/* not called with PIL > 10 */
845 		CPU_STATS_ADDQ(cp, sys, pswitch, 1);
846 		CPU_STATS_ADDQ(cp, sys, intrblk, 1);
847 		next = thread_unpin();
848 		TRACE_0(TR_FAC_DISP, TR_RESUME_START, "resume_start");
849 		resume_from_intr(next);
850 	} else {
851 #ifdef	DEBUG
852 		if (t->t_state == TS_ONPROC &&
853 		    t->t_disp_queue->disp_cpu == CPU &&
854 		    t->t_preempt == 0) {
855 			thread_lock(t);
856 			ASSERT(t->t_state != TS_ONPROC ||
857 			    t->t_disp_queue->disp_cpu != CPU ||
858 			    t->t_preempt != 0);	/* cannot migrate */
859 			thread_unlock_nopreempt(t);
860 		}
861 #endif	/* DEBUG */
862 		cp = CPU;
863 		next = disp();		/* returns with spl high */
864 		ASSERT(CPU_ON_INTR(cp) == 0);	/* not called with PIL > 10 */
865 
866 		/* OK to steal anything left on run queue */
867 		cp->cpu_disp_flags &= ~CPU_DISP_DONTSTEAL;
868 
869 		if (next != t) {
870 			if (t == cp->cpu_idle_thread) {
871 				PG_NRUN_UPDATE(cp, 1);
872 			} else if (next == cp->cpu_idle_thread) {
873 				PG_NRUN_UPDATE(cp, -1);
874 			}
875 
876 			/*
877 			 * If t was previously in the TS_ONPROC state,
878 			 * setfrontdq and setbackdq won't have set its t_waitrq.
879 			 * Since we now finally know that we're switching away
880 			 * from this thread, set its t_waitrq if it is on a run
881 			 * queue.
882 			 */
883 			if ((t->t_state == TS_RUN) && (t->t_waitrq == 0)) {
884 				t->t_waitrq = gethrtime_unscaled();
885 			}
886 
887 			/*
888 			 * restore mstate of thread that we are switching to
889 			 */
890 			restore_mstate(next);
891 
892 			CPU_STATS_ADDQ(cp, sys, pswitch, 1);
893 			cp->cpu_last_swtch = t->t_disp_time = lbolt;
894 			TRACE_0(TR_FAC_DISP, TR_RESUME_START, "resume_start");
895 
896 			if (dtrace_vtime_active)
897 				dtrace_vtime_switch(next);
898 
899 			resume(next);
900 			/*
901 			 * The TR_RESUME_END and TR_SWTCH_END trace points
902 			 * appear at the end of resume(), because we may not
903 			 * return here
904 			 */
905 		} else {
906 			if (t->t_flag & T_INTR_THREAD)
907 				cpu_intr_swtch_exit(t);
908 
909 			DTRACE_SCHED(remain__cpu);
910 			TRACE_0(TR_FAC_DISP, TR_SWTCH_END, "swtch_end");
911 			(void) spl0();
912 		}
913 	}
914 }
915 
916 /*
917  * swtch_from_zombie()
918  *	Special case of swtch(), which allows checks for TS_ZOMB to be
919  *	eliminated from normal resume.
920  *	Find best runnable thread and run it.
921  *	Called with the current thread zombied.
922  *	Zombies cannot migrate, so CPU references are safe.
923  */
924 void
925 swtch_from_zombie()
926 {
927 	kthread_t	*next;
928 	cpu_t		*cpu = CPU;
929 
930 	TRACE_0(TR_FAC_DISP, TR_SWTCH_START, "swtch_start");
931 
932 	ASSERT(curthread->t_state == TS_ZOMB);
933 
934 	next = disp();			/* returns with spl high */
935 	ASSERT(CPU_ON_INTR(CPU) == 0);	/* not called with PIL > 10 */
936 	CPU_STATS_ADDQ(CPU, sys, pswitch, 1);
937 	ASSERT(next != curthread);
938 	TRACE_0(TR_FAC_DISP, TR_RESUME_START, "resume_start");
939 
940 	if (next == cpu->cpu_idle_thread)
941 		PG_NRUN_UPDATE(cpu, -1);
942 
943 	restore_mstate(next);
944 
945 	if (dtrace_vtime_active)
946 		dtrace_vtime_switch(next);
947 
948 	resume_from_zombie(next);
949 	/*
950 	 * The TR_RESUME_END and TR_SWTCH_END trace points
951 	 * appear at the end of resume(), because we certainly will not
952 	 * return here
953 	 */
954 }
955 
956 #if defined(DEBUG) && (defined(DISP_DEBUG) || defined(lint))
957 static int
958 thread_on_queue(kthread_t *tp)
959 {
960 	cpu_t	*cp;
961 	cpu_t	*self;
962 	disp_t	*dp;
963 
964 	self = CPU;
965 	cp = self->cpu_next_onln;
966 	dp = cp->cpu_disp;
967 	for (;;) {
968 		dispq_t		*dq;
969 		dispq_t		*eq;
970 
971 		disp_lock_enter_high(&dp->disp_lock);
972 		for (dq = dp->disp_q, eq = dp->disp_q_limit; dq < eq; ++dq) {
973 			kthread_t	*rp;
974 
975 			ASSERT(dq->dq_last == NULL ||
976 				dq->dq_last->t_link == NULL);
977 			for (rp = dq->dq_first; rp; rp = rp->t_link)
978 				if (tp == rp) {
979 					disp_lock_exit_high(&dp->disp_lock);
980 					return (1);
981 				}
982 		}
983 		disp_lock_exit_high(&dp->disp_lock);
984 		if (cp == NULL)
985 			break;
986 		if (cp == self) {
987 			cp = NULL;
988 			dp = &cp->cpu_part->cp_kp_queue;
989 		} else {
990 			cp = cp->cpu_next_onln;
991 			dp = cp->cpu_disp;
992 		}
993 	}
994 	return (0);
995 }	/* end of thread_on_queue */
996 #else
997 
998 #define	thread_on_queue(tp)	0	/* ASSERT must be !thread_on_queue */
999 
1000 #endif  /* DEBUG */
1001 
1002 /*
1003  * like swtch(), but switch to a specified thread taken from another CPU.
1004  *	called with spl high..
1005  */
1006 void
1007 swtch_to(kthread_t *next)
1008 {
1009 	cpu_t			*cp = CPU;
1010 
1011 	TRACE_0(TR_FAC_DISP, TR_SWTCH_START, "swtch_start");
1012 
1013 	/*
1014 	 * Update context switch statistics.
1015 	 */
1016 	CPU_STATS_ADDQ(cp, sys, pswitch, 1);
1017 
1018 	TRACE_0(TR_FAC_DISP, TR_RESUME_START, "resume_start");
1019 
1020 	if (curthread == cp->cpu_idle_thread)
1021 		PG_NRUN_UPDATE(cp, 1);
1022 
1023 	/* OK to steal anything left on run queue */
1024 	cp->cpu_disp_flags &= ~CPU_DISP_DONTSTEAL;
1025 
1026 	/* record last execution time */
1027 	cp->cpu_last_swtch = curthread->t_disp_time = lbolt;
1028 
1029 	/*
1030 	 * If t was previously in the TS_ONPROC state, setfrontdq and setbackdq
1031 	 * won't have set its t_waitrq.  Since we now finally know that we're
1032 	 * switching away from this thread, set its t_waitrq if it is on a run
1033 	 * queue.
1034 	 */
1035 	if ((curthread->t_state == TS_RUN) && (curthread->t_waitrq == 0)) {
1036 		curthread->t_waitrq = gethrtime_unscaled();
1037 	}
1038 
1039 	/* restore next thread to previously running microstate */
1040 	restore_mstate(next);
1041 
1042 	if (dtrace_vtime_active)
1043 		dtrace_vtime_switch(next);
1044 
1045 	resume(next);
1046 	/*
1047 	 * The TR_RESUME_END and TR_SWTCH_END trace points
1048 	 * appear at the end of resume(), because we may not
1049 	 * return here
1050 	 */
1051 }
1052 
1053 
1054 
1055 #define	CPU_IDLING(pri)	((pri) == -1)
1056 
1057 static void
1058 cpu_resched(cpu_t *cp, pri_t tpri)
1059 {
1060 	int	call_poke_cpu = 0;
1061 	pri_t   cpupri = cp->cpu_dispatch_pri;
1062 
1063 	if (!CPU_IDLING(cpupri) && (cpupri < tpri)) {
1064 		TRACE_2(TR_FAC_DISP, TR_CPU_RESCHED,
1065 		    "CPU_RESCHED:Tpri %d Cpupri %d", tpri, cpupri);
1066 		if (tpri >= upreemptpri && cp->cpu_runrun == 0) {
1067 			cp->cpu_runrun = 1;
1068 			aston(cp->cpu_dispthread);
1069 			if (tpri < kpreemptpri && cp != CPU)
1070 				call_poke_cpu = 1;
1071 		}
1072 		if (tpri >= kpreemptpri && cp->cpu_kprunrun == 0) {
1073 			cp->cpu_kprunrun = 1;
1074 			if (cp != CPU)
1075 				call_poke_cpu = 1;
1076 		}
1077 	}
1078 
1079 	/*
1080 	 * Propagate cpu_runrun, and cpu_kprunrun to global visibility.
1081 	 */
1082 	membar_enter();
1083 
1084 	if (call_poke_cpu)
1085 		poke_cpu(cp->cpu_id);
1086 }
1087 
1088 /*
1089  * Perform multi-level CMT load balancing of running threads.
1090  * tp is the thread being enqueued
1091  * cp is the hint CPU (chosen by cpu_choose()).
1092  */
1093 static cpu_t *
1094 cmt_balance(kthread_t *tp, cpu_t *cp)
1095 {
1096 	int		hint, i, cpu;
1097 	int		self = 0;
1098 	group_t		*cmt_pgs, *siblings;
1099 	pg_cmt_t	*pg, *pg_tmp, *tpg = NULL;
1100 	int		pg_nrun, tpg_nrun;
1101 	int		level = 0;
1102 	cpu_t		*newcp;
1103 
1104 	ASSERT(THREAD_LOCK_HELD(tp));
1105 
1106 	cmt_pgs = &cp->cpu_pg->cmt_pgs;
1107 
1108 	if (GROUP_SIZE(cmt_pgs) == 0)
1109 		return (cp);	/* nothing to do */
1110 
1111 	if (tp == curthread)
1112 		self = 1;
1113 
1114 	/*
1115 	 * Balance across siblings in the CPUs CMT lineage
1116 	 */
1117 	do {
1118 		pg = GROUP_ACCESS(cmt_pgs, level);
1119 
1120 		pg_nrun = pg->cmt_nrunning;
1121 		if (self &&
1122 		    bitset_in_set(&pg->cmt_cpus_actv_set, CPU->cpu_seqid))
1123 			pg_nrun--;	/* Ignore curthread's effect */
1124 
1125 		siblings = pg->cmt_siblings;
1126 		hint = pg->cmt_hint;
1127 
1128 		/*
1129 		 * Check for validity of the hint
1130 		 * It should reference a valid sibling
1131 		 */
1132 		if (hint >= GROUP_SIZE(siblings))
1133 			hint = pg->cmt_hint = 0;
1134 		else
1135 			pg->cmt_hint++;
1136 
1137 		/*
1138 		 * Find a balancing candidate from among our siblings
1139 		 * "hint" is a hint for where to start looking
1140 		 */
1141 		i = hint;
1142 		do {
1143 			ASSERT(i < GROUP_SIZE(siblings));
1144 			pg_tmp = GROUP_ACCESS(siblings, i);
1145 
1146 			/*
1147 			 * The candidate must not be us, and must
1148 			 * have some CPU resources in the thread's
1149 			 * partition
1150 			 */
1151 			if (pg_tmp != pg &&
1152 			    bitset_in_set(&tp->t_cpupart->cp_cmt_pgs,
1153 			    ((pg_t *)pg_tmp)->pg_id)) {
1154 				tpg = pg_tmp;
1155 				break;
1156 			}
1157 
1158 			if (++i >= GROUP_SIZE(siblings))
1159 				i = 0;
1160 		} while (i != hint);
1161 
1162 		if (!tpg)
1163 			continue;	/* no candidates at this level */
1164 
1165 		/*
1166 		 * Check if the balancing target is underloaded
1167 		 * Decide to balance if the target is running fewer
1168 		 * threads, or if it's running the same number of threads
1169 		 * with more online CPUs
1170 		 */
1171 		tpg_nrun = tpg->cmt_nrunning;
1172 		if (pg_nrun > tpg_nrun ||
1173 		    (pg_nrun == tpg_nrun &&
1174 		    (GROUP_SIZE(&tpg->cmt_cpus_actv) >
1175 			GROUP_SIZE(&pg->cmt_cpus_actv)))) {
1176 			break;
1177 		}
1178 		tpg = NULL;
1179 	} while (++level < GROUP_SIZE(cmt_pgs));
1180 
1181 
1182 	if (tpg) {
1183 		/*
1184 		 * Select an idle CPU from the target PG
1185 		 */
1186 		for (cpu = 0; cpu < GROUP_SIZE(&tpg->cmt_cpus_actv); cpu++) {
1187 			newcp = GROUP_ACCESS(&tpg->cmt_cpus_actv, cpu);
1188 			if (newcp->cpu_part == tp->t_cpupart &&
1189 			    newcp->cpu_dispatch_pri == -1) {
1190 				cp = newcp;
1191 				break;
1192 			}
1193 		}
1194 	}
1195 
1196 	return (cp);
1197 }
1198 
1199 /*
1200  * setbackdq() keeps runqs balanced such that the difference in length
1201  * between the chosen runq and the next one is no more than RUNQ_MAX_DIFF.
1202  * For threads with priorities below RUNQ_MATCH_PRI levels, the runq's lengths
1203  * must match.  When per-thread TS_RUNQMATCH flag is set, setbackdq() will
1204  * try to keep runqs perfectly balanced regardless of the thread priority.
1205  */
1206 #define	RUNQ_MATCH_PRI	16	/* pri below which queue lengths must match */
1207 #define	RUNQ_MAX_DIFF	2	/* maximum runq length difference */
1208 #define	RUNQ_LEN(cp, pri)	((cp)->cpu_disp->disp_q[pri].dq_sruncnt)
1209 
1210 /*
1211  * Put the specified thread on the back of the dispatcher
1212  * queue corresponding to its current priority.
1213  *
1214  * Called with the thread in transition, onproc or stopped state
1215  * and locked (transition implies locked) and at high spl.
1216  * Returns with the thread in TS_RUN state and still locked.
1217  */
1218 void
1219 setbackdq(kthread_t *tp)
1220 {
1221 	dispq_t	*dq;
1222 	disp_t		*dp;
1223 	cpu_t		*cp;
1224 	pri_t		tpri;
1225 	int		bound;
1226 
1227 	ASSERT(THREAD_LOCK_HELD(tp));
1228 	ASSERT((tp->t_schedflag & TS_ALLSTART) == 0);
1229 	ASSERT(!thread_on_queue(tp));	/* make sure tp isn't on a runq */
1230 
1231 	/*
1232 	 * If thread is "swapped" or on the swap queue don't
1233 	 * queue it, but wake sched.
1234 	 */
1235 	if ((tp->t_schedflag & (TS_LOAD | TS_ON_SWAPQ)) != TS_LOAD) {
1236 		disp_swapped_setrun(tp);
1237 		return;
1238 	}
1239 
1240 	tpri = DISP_PRIO(tp);
1241 	if (ncpus == 1)
1242 		cp = tp->t_cpu;
1243 	else if (!tp->t_bound_cpu && !tp->t_weakbound_cpu) {
1244 		if (tpri >= kpqpri) {
1245 			setkpdq(tp, SETKP_BACK);
1246 			return;
1247 		}
1248 		/*
1249 		 * Let cpu_choose suggest a CPU.
1250 		 */
1251 		cp = cpu_choose(tp, tpri);
1252 
1253 		if (tp->t_cpupart == cp->cpu_part) {
1254 			int	qlen;
1255 
1256 			/*
1257 			 * Perform any CMT load balancing
1258 			 */
1259 			cp = cmt_balance(tp, cp);
1260 
1261 			/*
1262 			 * Balance across the run queues
1263 			 */
1264 			qlen = RUNQ_LEN(cp, tpri);
1265 			if (tpri >= RUNQ_MATCH_PRI &&
1266 			    !(tp->t_schedflag & TS_RUNQMATCH))
1267 				qlen -= RUNQ_MAX_DIFF;
1268 			if (qlen > 0) {
1269 				cpu_t *newcp;
1270 
1271 				if (tp->t_lpl->lpl_lgrpid == LGRP_ROOTID) {
1272 					newcp = cp->cpu_next_part;
1273 				} else if ((newcp = cp->cpu_next_lpl) == cp) {
1274 					newcp = cp->cpu_next_part;
1275 				}
1276 
1277 				if (RUNQ_LEN(newcp, tpri) < qlen) {
1278 					DTRACE_PROBE3(runq__balance,
1279 					    kthread_t *, tp,
1280 					    cpu_t *, cp, cpu_t *, newcp);
1281 					cp = newcp;
1282 				}
1283 			}
1284 		} else {
1285 			/*
1286 			 * Migrate to a cpu in the new partition.
1287 			 */
1288 			cp = disp_lowpri_cpu(tp->t_cpupart->cp_cpulist,
1289 			    tp->t_lpl, tp->t_pri, NULL);
1290 		}
1291 		bound = 0;
1292 		ASSERT((cp->cpu_flags & CPU_QUIESCED) == 0);
1293 	} else {
1294 		/*
1295 		 * It is possible that t_weakbound_cpu != t_bound_cpu (for
1296 		 * a short time until weak binding that existed when the
1297 		 * strong binding was established has dropped) so we must
1298 		 * favour weak binding over strong.
1299 		 */
1300 		cp = tp->t_weakbound_cpu ?
1301 		    tp->t_weakbound_cpu : tp->t_bound_cpu;
1302 		bound = 1;
1303 	}
1304 	/*
1305 	 * A thread that is ONPROC may be temporarily placed on the run queue
1306 	 * but then chosen to run again by disp.  If the thread we're placing on
1307 	 * the queue is in TS_ONPROC state, don't set its t_waitrq until a
1308 	 * replacement process is actually scheduled in swtch().  In this
1309 	 * situation, curthread is the only thread that could be in the ONPROC
1310 	 * state.
1311 	 */
1312 	if ((tp != curthread) && (tp->t_waitrq == 0)) {
1313 		hrtime_t curtime;
1314 
1315 		curtime = gethrtime_unscaled();
1316 		(void) cpu_update_pct(tp, curtime);
1317 		tp->t_waitrq = curtime;
1318 	} else {
1319 		(void) cpu_update_pct(tp, gethrtime_unscaled());
1320 	}
1321 
1322 	dp = cp->cpu_disp;
1323 	disp_lock_enter_high(&dp->disp_lock);
1324 
1325 	DTRACE_SCHED3(enqueue, kthread_t *, tp, disp_t *, dp, int, 0);
1326 	TRACE_3(TR_FAC_DISP, TR_BACKQ, "setbackdq:pri %d cpu %p tid %p",
1327 		tpri, cp, tp);
1328 
1329 #ifndef NPROBE
1330 	/* Kernel probe */
1331 	if (tnf_tracing_active)
1332 		tnf_thread_queue(tp, cp, tpri);
1333 #endif /* NPROBE */
1334 
1335 	ASSERT(tpri >= 0 && tpri < dp->disp_npri);
1336 
1337 	THREAD_RUN(tp, &dp->disp_lock);		/* set t_state to TS_RUN */
1338 	tp->t_disp_queue = dp;
1339 	tp->t_link = NULL;
1340 
1341 	dq = &dp->disp_q[tpri];
1342 	dp->disp_nrunnable++;
1343 	if (!bound)
1344 		dp->disp_steal = 0;
1345 	membar_enter();
1346 
1347 	if (dq->dq_sruncnt++ != 0) {
1348 		ASSERT(dq->dq_first != NULL);
1349 		dq->dq_last->t_link = tp;
1350 		dq->dq_last = tp;
1351 	} else {
1352 		ASSERT(dq->dq_first == NULL);
1353 		ASSERT(dq->dq_last == NULL);
1354 		dq->dq_first = dq->dq_last = tp;
1355 		BT_SET(dp->disp_qactmap, tpri);
1356 		if (tpri > dp->disp_maxrunpri) {
1357 			dp->disp_maxrunpri = tpri;
1358 			membar_enter();
1359 			cpu_resched(cp, tpri);
1360 		}
1361 	}
1362 
1363 	if (!bound && tpri > dp->disp_max_unbound_pri) {
1364 		if (tp == curthread && dp->disp_max_unbound_pri == -1 &&
1365 		    cp == CPU) {
1366 			/*
1367 			 * If there are no other unbound threads on the
1368 			 * run queue, don't allow other CPUs to steal
1369 			 * this thread while we are in the middle of a
1370 			 * context switch. We may just switch to it
1371 			 * again right away. CPU_DISP_DONTSTEAL is cleared
1372 			 * in swtch and swtch_to.
1373 			 */
1374 			cp->cpu_disp_flags |= CPU_DISP_DONTSTEAL;
1375 		}
1376 		dp->disp_max_unbound_pri = tpri;
1377 	}
1378 	(*disp_enq_thread)(cp, bound);
1379 }
1380 
1381 /*
1382  * Put the specified thread on the front of the dispatcher
1383  * queue corresponding to its current priority.
1384  *
1385  * Called with the thread in transition, onproc or stopped state
1386  * and locked (transition implies locked) and at high spl.
1387  * Returns with the thread in TS_RUN state and still locked.
1388  */
1389 void
1390 setfrontdq(kthread_t *tp)
1391 {
1392 	disp_t		*dp;
1393 	dispq_t		*dq;
1394 	cpu_t		*cp;
1395 	pri_t		tpri;
1396 	int		bound;
1397 
1398 	ASSERT(THREAD_LOCK_HELD(tp));
1399 	ASSERT((tp->t_schedflag & TS_ALLSTART) == 0);
1400 	ASSERT(!thread_on_queue(tp));	/* make sure tp isn't on a runq */
1401 
1402 	/*
1403 	 * If thread is "swapped" or on the swap queue don't
1404 	 * queue it, but wake sched.
1405 	 */
1406 	if ((tp->t_schedflag & (TS_LOAD | TS_ON_SWAPQ)) != TS_LOAD) {
1407 		disp_swapped_setrun(tp);
1408 		return;
1409 	}
1410 
1411 	tpri = DISP_PRIO(tp);
1412 	if (ncpus == 1)
1413 		cp = tp->t_cpu;
1414 	else if (!tp->t_bound_cpu && !tp->t_weakbound_cpu) {
1415 		if (tpri >= kpqpri) {
1416 			setkpdq(tp, SETKP_FRONT);
1417 			return;
1418 		}
1419 		cp = tp->t_cpu;
1420 		if (tp->t_cpupart == cp->cpu_part) {
1421 			/*
1422 			 * If we are of higher or equal priority than
1423 			 * the highest priority runnable thread of
1424 			 * the current CPU, just pick this CPU.  Otherwise
1425 			 * Let cpu_choose() select the CPU.  If this cpu
1426 			 * is the target of an offline request then do not
1427 			 * pick it - a thread_nomigrate() on the in motion
1428 			 * cpu relies on this when it forces a preempt.
1429 			 */
1430 			if (tpri < cp->cpu_disp->disp_maxrunpri ||
1431 			    cp == cpu_inmotion)
1432 				cp = cpu_choose(tp, tpri);
1433 		} else {
1434 			/*
1435 			 * Migrate to a cpu in the new partition.
1436 			 */
1437 			cp = disp_lowpri_cpu(tp->t_cpupart->cp_cpulist,
1438 			    tp->t_lpl, tp->t_pri, NULL);
1439 		}
1440 		bound = 0;
1441 		ASSERT((cp->cpu_flags & CPU_QUIESCED) == 0);
1442 	} else {
1443 		/*
1444 		 * It is possible that t_weakbound_cpu != t_bound_cpu (for
1445 		 * a short time until weak binding that existed when the
1446 		 * strong binding was established has dropped) so we must
1447 		 * favour weak binding over strong.
1448 		 */
1449 		cp = tp->t_weakbound_cpu ?
1450 		    tp->t_weakbound_cpu : tp->t_bound_cpu;
1451 		bound = 1;
1452 	}
1453 
1454 	/*
1455 	 * A thread that is ONPROC may be temporarily placed on the run queue
1456 	 * but then chosen to run again by disp.  If the thread we're placing on
1457 	 * the queue is in TS_ONPROC state, don't set its t_waitrq until a
1458 	 * replacement process is actually scheduled in swtch().  In this
1459 	 * situation, curthread is the only thread that could be in the ONPROC
1460 	 * state.
1461 	 */
1462 	if ((tp != curthread) && (tp->t_waitrq == 0)) {
1463 		hrtime_t curtime;
1464 
1465 		curtime = gethrtime_unscaled();
1466 		(void) cpu_update_pct(tp, curtime);
1467 		tp->t_waitrq = curtime;
1468 	} else {
1469 		(void) cpu_update_pct(tp, gethrtime_unscaled());
1470 	}
1471 
1472 	dp = cp->cpu_disp;
1473 	disp_lock_enter_high(&dp->disp_lock);
1474 
1475 	TRACE_2(TR_FAC_DISP, TR_FRONTQ, "frontq:pri %d tid %p", tpri, tp);
1476 	DTRACE_SCHED3(enqueue, kthread_t *, tp, disp_t *, dp, int, 1);
1477 
1478 #ifndef NPROBE
1479 	/* Kernel probe */
1480 	if (tnf_tracing_active)
1481 		tnf_thread_queue(tp, cp, tpri);
1482 #endif /* NPROBE */
1483 
1484 	ASSERT(tpri >= 0 && tpri < dp->disp_npri);
1485 
1486 	THREAD_RUN(tp, &dp->disp_lock);		/* set TS_RUN state and lock */
1487 	tp->t_disp_queue = dp;
1488 
1489 	dq = &dp->disp_q[tpri];
1490 	dp->disp_nrunnable++;
1491 	if (!bound)
1492 		dp->disp_steal = 0;
1493 	membar_enter();
1494 
1495 	if (dq->dq_sruncnt++ != 0) {
1496 		ASSERT(dq->dq_last != NULL);
1497 		tp->t_link = dq->dq_first;
1498 		dq->dq_first = tp;
1499 	} else {
1500 		ASSERT(dq->dq_last == NULL);
1501 		ASSERT(dq->dq_first == NULL);
1502 		tp->t_link = NULL;
1503 		dq->dq_first = dq->dq_last = tp;
1504 		BT_SET(dp->disp_qactmap, tpri);
1505 		if (tpri > dp->disp_maxrunpri) {
1506 			dp->disp_maxrunpri = tpri;
1507 			membar_enter();
1508 			cpu_resched(cp, tpri);
1509 		}
1510 	}
1511 
1512 	if (!bound && tpri > dp->disp_max_unbound_pri) {
1513 		if (tp == curthread && dp->disp_max_unbound_pri == -1 &&
1514 		    cp == CPU) {
1515 			/*
1516 			 * If there are no other unbound threads on the
1517 			 * run queue, don't allow other CPUs to steal
1518 			 * this thread while we are in the middle of a
1519 			 * context switch. We may just switch to it
1520 			 * again right away. CPU_DISP_DONTSTEAL is cleared
1521 			 * in swtch and swtch_to.
1522 			 */
1523 			cp->cpu_disp_flags |= CPU_DISP_DONTSTEAL;
1524 		}
1525 		dp->disp_max_unbound_pri = tpri;
1526 	}
1527 	(*disp_enq_thread)(cp, bound);
1528 }
1529 
1530 /*
1531  * Put a high-priority unbound thread on the kp queue
1532  */
1533 static void
1534 setkpdq(kthread_t *tp, int borf)
1535 {
1536 	dispq_t	*dq;
1537 	disp_t	*dp;
1538 	cpu_t	*cp;
1539 	pri_t	tpri;
1540 
1541 	tpri = DISP_PRIO(tp);
1542 
1543 	dp = &tp->t_cpupart->cp_kp_queue;
1544 	disp_lock_enter_high(&dp->disp_lock);
1545 
1546 	TRACE_2(TR_FAC_DISP, TR_FRONTQ, "frontq:pri %d tid %p", tpri, tp);
1547 
1548 	ASSERT(tpri >= 0 && tpri < dp->disp_npri);
1549 	DTRACE_SCHED3(enqueue, kthread_t *, tp, disp_t *, dp, int, borf);
1550 	THREAD_RUN(tp, &dp->disp_lock);		/* set t_state to TS_RUN */
1551 	tp->t_disp_queue = dp;
1552 	dp->disp_nrunnable++;
1553 	dq = &dp->disp_q[tpri];
1554 
1555 	if (dq->dq_sruncnt++ != 0) {
1556 		if (borf == SETKP_BACK) {
1557 			ASSERT(dq->dq_first != NULL);
1558 			tp->t_link = NULL;
1559 			dq->dq_last->t_link = tp;
1560 			dq->dq_last = tp;
1561 		} else {
1562 			ASSERT(dq->dq_last != NULL);
1563 			tp->t_link = dq->dq_first;
1564 			dq->dq_first = tp;
1565 		}
1566 	} else {
1567 		if (borf == SETKP_BACK) {
1568 			ASSERT(dq->dq_first == NULL);
1569 			ASSERT(dq->dq_last == NULL);
1570 			dq->dq_first = dq->dq_last = tp;
1571 		} else {
1572 			ASSERT(dq->dq_last == NULL);
1573 			ASSERT(dq->dq_first == NULL);
1574 			tp->t_link = NULL;
1575 			dq->dq_first = dq->dq_last = tp;
1576 		}
1577 		BT_SET(dp->disp_qactmap, tpri);
1578 		if (tpri > dp->disp_max_unbound_pri)
1579 			dp->disp_max_unbound_pri = tpri;
1580 		if (tpri > dp->disp_maxrunpri) {
1581 			dp->disp_maxrunpri = tpri;
1582 			membar_enter();
1583 		}
1584 	}
1585 
1586 	cp = tp->t_cpu;
1587 	if (tp->t_cpupart != cp->cpu_part) {
1588 		/* migrate to a cpu in the new partition */
1589 		cp = tp->t_cpupart->cp_cpulist;
1590 	}
1591 	cp = disp_lowpri_cpu(cp, tp->t_lpl, tp->t_pri, NULL);
1592 	disp_lock_enter_high(&cp->cpu_disp->disp_lock);
1593 	ASSERT((cp->cpu_flags & CPU_QUIESCED) == 0);
1594 
1595 #ifndef NPROBE
1596 	/* Kernel probe */
1597 	if (tnf_tracing_active)
1598 		tnf_thread_queue(tp, cp, tpri);
1599 #endif /* NPROBE */
1600 
1601 	if (cp->cpu_chosen_level < tpri)
1602 		cp->cpu_chosen_level = tpri;
1603 	cpu_resched(cp, tpri);
1604 	disp_lock_exit_high(&cp->cpu_disp->disp_lock);
1605 	(*disp_enq_thread)(cp, 0);
1606 }
1607 
1608 /*
1609  * Remove a thread from the dispatcher queue if it is on it.
1610  * It is not an error if it is not found but we return whether
1611  * or not it was found in case the caller wants to check.
1612  */
1613 int
1614 dispdeq(kthread_t *tp)
1615 {
1616 	disp_t		*dp;
1617 	dispq_t		*dq;
1618 	kthread_t	*rp;
1619 	kthread_t	*trp;
1620 	kthread_t	**ptp;
1621 	int		tpri;
1622 
1623 	ASSERT(THREAD_LOCK_HELD(tp));
1624 
1625 	if (tp->t_state != TS_RUN)
1626 		return (0);
1627 
1628 	/*
1629 	 * The thread is "swapped" or is on the swap queue and
1630 	 * hence no longer on the run queue, so return true.
1631 	 */
1632 	if ((tp->t_schedflag & (TS_LOAD | TS_ON_SWAPQ)) != TS_LOAD)
1633 		return (1);
1634 
1635 	tpri = DISP_PRIO(tp);
1636 	dp = tp->t_disp_queue;
1637 	ASSERT(tpri < dp->disp_npri);
1638 	dq = &dp->disp_q[tpri];
1639 	ptp = &dq->dq_first;
1640 	rp = *ptp;
1641 	trp = NULL;
1642 
1643 	ASSERT(dq->dq_last == NULL || dq->dq_last->t_link == NULL);
1644 
1645 	/*
1646 	 * Search for thread in queue.
1647 	 * Double links would simplify this at the expense of disp/setrun.
1648 	 */
1649 	while (rp != tp && rp != NULL) {
1650 		trp = rp;
1651 		ptp = &trp->t_link;
1652 		rp = trp->t_link;
1653 	}
1654 
1655 	if (rp == NULL) {
1656 		panic("dispdeq: thread not on queue");
1657 	}
1658 
1659 	DTRACE_SCHED2(dequeue, kthread_t *, tp, disp_t *, dp);
1660 
1661 	/*
1662 	 * Found it so remove it from queue.
1663 	 */
1664 	if ((*ptp = rp->t_link) == NULL)
1665 		dq->dq_last = trp;
1666 
1667 	dp->disp_nrunnable--;
1668 	if (--dq->dq_sruncnt == 0) {
1669 		dp->disp_qactmap[tpri >> BT_ULSHIFT] &= ~BT_BIW(tpri);
1670 		if (dp->disp_nrunnable == 0) {
1671 			dp->disp_max_unbound_pri = -1;
1672 			dp->disp_maxrunpri = -1;
1673 		} else if (tpri == dp->disp_maxrunpri) {
1674 			int ipri;
1675 
1676 			ipri = bt_gethighbit(dp->disp_qactmap,
1677 			    dp->disp_maxrunpri >> BT_ULSHIFT);
1678 			if (ipri < dp->disp_max_unbound_pri)
1679 				dp->disp_max_unbound_pri = ipri;
1680 			dp->disp_maxrunpri = ipri;
1681 		}
1682 	}
1683 	tp->t_link = NULL;
1684 	THREAD_TRANSITION(tp);		/* put in intermediate state */
1685 	return (1);
1686 }
1687 
1688 
1689 /*
1690  * dq_sruninc and dq_srundec are public functions for
1691  * incrementing/decrementing the sruncnts when a thread on
1692  * a dispatcher queue is made schedulable/unschedulable by
1693  * resetting the TS_LOAD flag.
1694  *
1695  * The caller MUST have the thread lock and therefore the dispatcher
1696  * queue lock so that the operation which changes
1697  * the flag, the operation that checks the status of the thread to
1698  * determine if it's on a disp queue AND the call to this function
1699  * are one atomic operation with respect to interrupts.
1700  */
1701 
1702 /*
1703  * Called by sched AFTER TS_LOAD flag is set on a swapped, runnable thread.
1704  */
1705 void
1706 dq_sruninc(kthread_t *t)
1707 {
1708 	ASSERT(t->t_state == TS_RUN);
1709 	ASSERT(t->t_schedflag & TS_LOAD);
1710 
1711 	THREAD_TRANSITION(t);
1712 	setfrontdq(t);
1713 }
1714 
1715 /*
1716  * See comment on calling conventions above.
1717  * Called by sched BEFORE TS_LOAD flag is cleared on a runnable thread.
1718  */
1719 void
1720 dq_srundec(kthread_t *t)
1721 {
1722 	ASSERT(t->t_schedflag & TS_LOAD);
1723 
1724 	(void) dispdeq(t);
1725 	disp_swapped_enq(t);
1726 }
1727 
1728 /*
1729  * Change the dispatcher lock of thread to the "swapped_lock"
1730  * and return with thread lock still held.
1731  *
1732  * Called with thread_lock held, in transition state, and at high spl.
1733  */
1734 void
1735 disp_swapped_enq(kthread_t *tp)
1736 {
1737 	ASSERT(THREAD_LOCK_HELD(tp));
1738 	ASSERT(tp->t_schedflag & TS_LOAD);
1739 
1740 	switch (tp->t_state) {
1741 	case TS_RUN:
1742 		disp_lock_enter_high(&swapped_lock);
1743 		THREAD_SWAP(tp, &swapped_lock);	/* set TS_RUN state and lock */
1744 		break;
1745 	case TS_ONPROC:
1746 		disp_lock_enter_high(&swapped_lock);
1747 		THREAD_TRANSITION(tp);
1748 		wake_sched_sec = 1;		/* tell clock to wake sched */
1749 		THREAD_SWAP(tp, &swapped_lock);	/* set TS_RUN state and lock */
1750 		break;
1751 	default:
1752 		panic("disp_swapped: tp: %p bad t_state", (void *)tp);
1753 	}
1754 }
1755 
1756 /*
1757  * This routine is called by setbackdq/setfrontdq if the thread is
1758  * not loaded or loaded and on the swap queue.
1759  *
1760  * Thread state TS_SLEEP implies that a swapped thread
1761  * has been woken up and needs to be swapped in by the swapper.
1762  *
1763  * Thread state TS_RUN, it implies that the priority of a swapped
1764  * thread is being increased by scheduling class (e.g. ts_update).
1765  */
1766 static void
1767 disp_swapped_setrun(kthread_t *tp)
1768 {
1769 	ASSERT(THREAD_LOCK_HELD(tp));
1770 	ASSERT((tp->t_schedflag & (TS_LOAD | TS_ON_SWAPQ)) != TS_LOAD);
1771 
1772 	switch (tp->t_state) {
1773 	case TS_SLEEP:
1774 		disp_lock_enter_high(&swapped_lock);
1775 		/*
1776 		 * Wakeup sched immediately (i.e., next tick) if the
1777 		 * thread priority is above maxclsyspri.
1778 		 */
1779 		if (DISP_PRIO(tp) > maxclsyspri)
1780 			wake_sched = 1;
1781 		else
1782 			wake_sched_sec = 1;
1783 		THREAD_RUN(tp, &swapped_lock); /* set TS_RUN state and lock */
1784 		break;
1785 	case TS_RUN:				/* called from ts_update */
1786 		break;
1787 	default:
1788 		panic("disp_swapped_setrun: tp: %p bad t_state", tp);
1789 	}
1790 }
1791 
1792 
1793 /*
1794  *	Make a thread give up its processor.  Find the processor on
1795  *	which this thread is executing, and have that processor
1796  *	preempt.
1797  */
1798 void
1799 cpu_surrender(kthread_t *tp)
1800 {
1801 	cpu_t	*cpup;
1802 	int	max_pri;
1803 	int	max_run_pri;
1804 	klwp_t	*lwp;
1805 
1806 	ASSERT(THREAD_LOCK_HELD(tp));
1807 
1808 	if (tp->t_state != TS_ONPROC)
1809 		return;
1810 	cpup = tp->t_disp_queue->disp_cpu;	/* CPU thread dispatched to */
1811 	max_pri = cpup->cpu_disp->disp_maxrunpri; /* best pri of that CPU */
1812 	max_run_pri = CP_MAXRUNPRI(cpup->cpu_part);
1813 	if (max_pri < max_run_pri)
1814 		max_pri = max_run_pri;
1815 
1816 	cpup->cpu_runrun = 1;
1817 	if (max_pri >= kpreemptpri && cpup->cpu_kprunrun == 0) {
1818 		cpup->cpu_kprunrun = 1;
1819 	}
1820 
1821 	/*
1822 	 * Propagate cpu_runrun, and cpu_kprunrun to global visibility.
1823 	 */
1824 	membar_enter();
1825 
1826 	DTRACE_SCHED1(surrender, kthread_t *, tp);
1827 
1828 	/*
1829 	 * Make the target thread take an excursion through trap()
1830 	 * to do preempt() (unless we're already in trap or post_syscall,
1831 	 * calling cpu_surrender via CL_TRAPRET).
1832 	 */
1833 	if (tp != curthread || (lwp = tp->t_lwp) == NULL ||
1834 	    lwp->lwp_state != LWP_USER) {
1835 		aston(tp);
1836 		if (cpup != CPU)
1837 			poke_cpu(cpup->cpu_id);
1838 	}
1839 	TRACE_2(TR_FAC_DISP, TR_CPU_SURRENDER,
1840 	    "cpu_surrender:tid %p cpu %p", tp, cpup);
1841 }
1842 
1843 
1844 /*
1845  * Commit to and ratify a scheduling decision
1846  */
1847 /*ARGSUSED*/
1848 static kthread_t *
1849 disp_ratify(kthread_t *tp, disp_t *kpq)
1850 {
1851 	pri_t	tpri, maxpri;
1852 	pri_t	maxkpri;
1853 	cpu_t	*cpup;
1854 
1855 	ASSERT(tp != NULL);
1856 	/*
1857 	 * Commit to, then ratify scheduling decision
1858 	 */
1859 	cpup = CPU;
1860 	if (cpup->cpu_runrun != 0)
1861 		cpup->cpu_runrun = 0;
1862 	if (cpup->cpu_kprunrun != 0)
1863 		cpup->cpu_kprunrun = 0;
1864 	if (cpup->cpu_chosen_level != -1)
1865 		cpup->cpu_chosen_level = -1;
1866 	membar_enter();
1867 	tpri = DISP_PRIO(tp);
1868 	maxpri = cpup->cpu_disp->disp_maxrunpri;
1869 	maxkpri = kpq->disp_maxrunpri;
1870 	if (maxpri < maxkpri)
1871 		maxpri = maxkpri;
1872 	if (tpri < maxpri) {
1873 		/*
1874 		 * should have done better
1875 		 * put this one back and indicate to try again
1876 		 */
1877 		cpup->cpu_dispthread = curthread;	/* fixup dispthread */
1878 		cpup->cpu_dispatch_pri = DISP_PRIO(curthread);
1879 		thread_lock_high(tp);
1880 		THREAD_TRANSITION(tp);
1881 		setfrontdq(tp);
1882 		thread_unlock_nopreempt(tp);
1883 
1884 		tp = NULL;
1885 	}
1886 	return (tp);
1887 }
1888 
1889 /*
1890  * See if there is any work on the dispatcher queue for other CPUs.
1891  * If there is, dequeue the best thread and return.
1892  */
1893 static kthread_t *
1894 disp_getwork(cpu_t *cp)
1895 {
1896 	cpu_t		*ocp;		/* other CPU */
1897 	cpu_t		*ocp_start;
1898 	cpu_t		*tcp;		/* target local CPU */
1899 	kthread_t	*tp;
1900 	kthread_t	*retval = NULL;
1901 	pri_t		maxpri;
1902 	disp_t		*kpq;		/* kp queue for this partition */
1903 	lpl_t		*lpl, *lpl_leaf;
1904 	int		hint, leafidx;
1905 	hrtime_t	stealtime;
1906 
1907 	maxpri = -1;
1908 	tcp = NULL;
1909 
1910 	kpq = &cp->cpu_part->cp_kp_queue;
1911 	while (kpq->disp_maxrunpri >= 0) {
1912 		/*
1913 		 * Try to take a thread from the kp_queue.
1914 		 */
1915 		tp = (disp_getbest(kpq));
1916 		if (tp)
1917 			return (disp_ratify(tp, kpq));
1918 	}
1919 
1920 	kpreempt_disable();		/* protect the cpu_active list */
1921 
1922 	/*
1923 	 * Try to find something to do on another CPU's run queue.
1924 	 * Loop through all other CPUs looking for the one with the highest
1925 	 * priority unbound thread.
1926 	 *
1927 	 * On NUMA machines, the partition's CPUs are consulted in order of
1928 	 * distance from the current CPU. This way, the first available
1929 	 * work found is also the closest, and will suffer the least
1930 	 * from being migrated.
1931 	 */
1932 	lpl = lpl_leaf = cp->cpu_lpl;
1933 	hint = leafidx = 0;
1934 
1935 	/*
1936 	 * This loop traverses the lpl hierarchy. Higher level lpls represent
1937 	 * broader levels of locality
1938 	 */
1939 	do {
1940 		/* This loop iterates over the lpl's leaves */
1941 		do {
1942 			if (lpl_leaf != cp->cpu_lpl)
1943 				ocp = lpl_leaf->lpl_cpus;
1944 			else
1945 				ocp = cp->cpu_next_lpl;
1946 
1947 			/* This loop iterates over the CPUs in the leaf */
1948 			ocp_start = ocp;
1949 			do {
1950 				pri_t pri;
1951 
1952 				ASSERT(CPU_ACTIVE(ocp));
1953 
1954 				/*
1955 				 * End our stroll around this lpl if:
1956 				 *
1957 				 * - Something became runnable on the local
1958 				 *   queue...which also ends our stroll around
1959 				 *   the partition.
1960 				 *
1961 				 * - We happen across another idle CPU.
1962 				 *   Since it is patrolling the next portion
1963 				 *   of the lpl's list (assuming it's not
1964 				 *   halted), move to the next higher level
1965 				 *   of locality.
1966 				 */
1967 				if (cp->cpu_disp->disp_nrunnable != 0) {
1968 					kpreempt_enable();
1969 					return (NULL);
1970 				}
1971 				if (ocp->cpu_dispatch_pri == -1) {
1972 					if (ocp->cpu_disp_flags &
1973 					    CPU_DISP_HALTED)
1974 						continue;
1975 					else
1976 						break;
1977 				}
1978 
1979 				/*
1980 				 * If there's only one thread and the CPU
1981 				 * is in the middle of a context switch,
1982 				 * or it's currently running the idle thread,
1983 				 * don't steal it.
1984 				 */
1985 				if ((ocp->cpu_disp_flags &
1986 					CPU_DISP_DONTSTEAL) &&
1987 				    ocp->cpu_disp->disp_nrunnable == 1)
1988 					continue;
1989 
1990 				pri = ocp->cpu_disp->disp_max_unbound_pri;
1991 				if (pri > maxpri) {
1992 					/*
1993 					 * Don't steal threads that we attempted
1994 					 * to steal recently until they're ready
1995 					 * to be stolen again.
1996 					 */
1997 					stealtime = ocp->cpu_disp->disp_steal;
1998 					if (stealtime == 0 ||
1999 					    stealtime - gethrtime() <= 0) {
2000 						maxpri = pri;
2001 						tcp = ocp;
2002 					} else {
2003 						/*
2004 						 * Don't update tcp, just set
2005 						 * the retval to T_DONTSTEAL, so
2006 						 * that if no acceptable CPUs
2007 						 * are found the return value
2008 						 * will be T_DONTSTEAL rather
2009 						 * then NULL.
2010 						 */
2011 						retval = T_DONTSTEAL;
2012 					}
2013 				}
2014 			} while ((ocp = ocp->cpu_next_lpl) != ocp_start);
2015 
2016 			if ((lpl_leaf = lpl->lpl_rset[++leafidx]) == NULL) {
2017 				leafidx = 0;
2018 				lpl_leaf = lpl->lpl_rset[leafidx];
2019 			}
2020 		} while (leafidx != hint);
2021 
2022 		hint = leafidx = lpl->lpl_hint;
2023 		if ((lpl = lpl->lpl_parent) != NULL)
2024 			lpl_leaf = lpl->lpl_rset[hint];
2025 	} while (!tcp && lpl);
2026 
2027 	kpreempt_enable();
2028 
2029 	/*
2030 	 * If another queue looks good, and there is still nothing on
2031 	 * the local queue, try to transfer one or more threads
2032 	 * from it to our queue.
2033 	 */
2034 	if (tcp && cp->cpu_disp->disp_nrunnable == 0) {
2035 		tp = disp_getbest(tcp->cpu_disp);
2036 		if (tp == NULL || tp == T_DONTSTEAL)
2037 			return (tp);
2038 		return (disp_ratify(tp, kpq));
2039 	}
2040 	return (retval);
2041 }
2042 
2043 
2044 /*
2045  * disp_fix_unbound_pri()
2046  *	Determines the maximum priority of unbound threads on the queue.
2047  *	The priority is kept for the queue, but is only increased, never
2048  *	reduced unless some CPU is looking for something on that queue.
2049  *
2050  *	The priority argument is the known upper limit.
2051  *
2052  *	Perhaps this should be kept accurately, but that probably means
2053  *	separate bitmaps for bound and unbound threads.  Since only idled
2054  *	CPUs will have to do this recalculation, it seems better this way.
2055  */
2056 static void
2057 disp_fix_unbound_pri(disp_t *dp, pri_t pri)
2058 {
2059 	kthread_t	*tp;
2060 	dispq_t		*dq;
2061 	ulong_t		*dqactmap = dp->disp_qactmap;
2062 	ulong_t		mapword;
2063 	int		wx;
2064 
2065 	ASSERT(DISP_LOCK_HELD(&dp->disp_lock));
2066 
2067 	ASSERT(pri >= 0);			/* checked by caller */
2068 
2069 	/*
2070 	 * Start the search at the next lowest priority below the supplied
2071 	 * priority.  This depends on the bitmap implementation.
2072 	 */
2073 	do {
2074 		wx = pri >> BT_ULSHIFT;		/* index of word in map */
2075 
2076 		/*
2077 		 * Form mask for all lower priorities in the word.
2078 		 */
2079 		mapword = dqactmap[wx] & (BT_BIW(pri) - 1);
2080 
2081 		/*
2082 		 * Get next lower active priority.
2083 		 */
2084 		if (mapword != 0) {
2085 			pri = (wx << BT_ULSHIFT) + highbit(mapword) - 1;
2086 		} else if (wx > 0) {
2087 			pri = bt_gethighbit(dqactmap, wx - 1); /* sign extend */
2088 			if (pri < 0)
2089 				break;
2090 		} else {
2091 			pri = -1;
2092 			break;
2093 		}
2094 
2095 		/*
2096 		 * Search the queue for unbound, runnable threads.
2097 		 */
2098 		dq = &dp->disp_q[pri];
2099 		tp = dq->dq_first;
2100 
2101 		while (tp && (tp->t_bound_cpu || tp->t_weakbound_cpu)) {
2102 			tp = tp->t_link;
2103 		}
2104 
2105 		/*
2106 		 * If a thread was found, set the priority and return.
2107 		 */
2108 	} while (tp == NULL);
2109 
2110 	/*
2111 	 * pri holds the maximum unbound thread priority or -1.
2112 	 */
2113 	if (dp->disp_max_unbound_pri != pri)
2114 		dp->disp_max_unbound_pri = pri;
2115 }
2116 
2117 /*
2118  * disp_adjust_unbound_pri() - thread is becoming unbound, so we should
2119  * 	check if the CPU to which is was previously bound should have
2120  * 	its disp_max_unbound_pri increased.
2121  */
2122 void
2123 disp_adjust_unbound_pri(kthread_t *tp)
2124 {
2125 	disp_t *dp;
2126 	pri_t tpri;
2127 
2128 	ASSERT(THREAD_LOCK_HELD(tp));
2129 
2130 	/*
2131 	 * Don't do anything if the thread is not bound, or
2132 	 * currently not runnable or swapped out.
2133 	 */
2134 	if (tp->t_bound_cpu == NULL ||
2135 	    tp->t_state != TS_RUN ||
2136 	    tp->t_schedflag & TS_ON_SWAPQ)
2137 		return;
2138 
2139 	tpri = DISP_PRIO(tp);
2140 	dp = tp->t_bound_cpu->cpu_disp;
2141 	ASSERT(tpri >= 0 && tpri < dp->disp_npri);
2142 	if (tpri > dp->disp_max_unbound_pri)
2143 		dp->disp_max_unbound_pri = tpri;
2144 }
2145 
2146 /*
2147  * disp_getbest()
2148  *   De-queue the highest priority unbound runnable thread.
2149  *   Returns with the thread unlocked and onproc but at splhigh (like disp()).
2150  *   Returns NULL if nothing found.
2151  *   Returns T_DONTSTEAL if the thread was not stealable.
2152  *   so that the caller will try again later.
2153  *
2154  *   Passed a pointer to a dispatch queue not associated with this CPU, and
2155  *   its type.
2156  */
2157 static kthread_t *
2158 disp_getbest(disp_t *dp)
2159 {
2160 	kthread_t	*tp;
2161 	dispq_t		*dq;
2162 	pri_t		pri;
2163 	cpu_t		*cp, *tcp;
2164 	boolean_t	allbound;
2165 
2166 	disp_lock_enter(&dp->disp_lock);
2167 
2168 	/*
2169 	 * If there is nothing to run, or the CPU is in the middle of a
2170 	 * context switch of the only thread, return NULL.
2171 	 */
2172 	tcp = dp->disp_cpu;
2173 	cp = CPU;
2174 	pri = dp->disp_max_unbound_pri;
2175 	if (pri == -1 ||
2176 	    (tcp != NULL && (tcp->cpu_disp_flags & CPU_DISP_DONTSTEAL) &&
2177 	    tcp->cpu_disp->disp_nrunnable == 1)) {
2178 		disp_lock_exit_nopreempt(&dp->disp_lock);
2179 		return (NULL);
2180 	}
2181 
2182 	dq = &dp->disp_q[pri];
2183 
2184 
2185 	/*
2186 	 * Assume that all threads are bound on this queue, and change it
2187 	 * later when we find out that it is not the case.
2188 	 */
2189 	allbound = B_TRUE;
2190 	for (tp = dq->dq_first; tp != NULL; tp = tp->t_link) {
2191 		hrtime_t now, nosteal, rqtime;
2192 
2193 		/*
2194 		 * Skip over bound threads which could be here even
2195 		 * though disp_max_unbound_pri indicated this level.
2196 		 */
2197 		if (tp->t_bound_cpu || tp->t_weakbound_cpu)
2198 			continue;
2199 
2200 		/*
2201 		 * We've got some unbound threads on this queue, so turn
2202 		 * the allbound flag off now.
2203 		 */
2204 		allbound = B_FALSE;
2205 
2206 		/*
2207 		 * The thread is a candidate for stealing from its run queue. We
2208 		 * don't want to steal threads that became runnable just a
2209 		 * moment ago. This improves CPU affinity for threads that get
2210 		 * preempted for short periods of time and go back on the run
2211 		 * queue.
2212 		 *
2213 		 * We want to let it stay on its run queue if it was only placed
2214 		 * there recently and it was running on the same CPU before that
2215 		 * to preserve its cache investment. For the thread to remain on
2216 		 * its run queue, ALL of the following conditions must be
2217 		 * satisfied:
2218 		 *
2219 		 * - the disp queue should not be the kernel preemption queue
2220 		 * - delayed idle stealing should not be disabled
2221 		 * - nosteal_nsec should be non-zero
2222 		 * - it should run with user priority
2223 		 * - it should be on the run queue of the CPU where it was
2224 		 *   running before being placed on the run queue
2225 		 * - it should be the only thread on the run queue (to prevent
2226 		 *   extra scheduling latency for other threads)
2227 		 * - it should sit on the run queue for less than per-chip
2228 		 *   nosteal interval or global nosteal interval
2229 		 * - in case of CPUs with shared cache it should sit in a run
2230 		 *   queue of a CPU from a different chip
2231 		 *
2232 		 * The checks are arranged so that the ones that are faster are
2233 		 * placed earlier.
2234 		 */
2235 		if (tcp == NULL ||
2236 		    pri >= minclsyspri ||
2237 		    tp->t_cpu != tcp)
2238 			break;
2239 
2240 		/*
2241 		 * Steal immediately if, due to CMT processor architecture
2242 		 * migraiton between cp and tcp would incur no performance
2243 		 * penalty.
2244 		 */
2245 		if (pg_cmt_can_migrate(cp, tcp))
2246 			break;
2247 
2248 		nosteal = nosteal_nsec;
2249 		if (nosteal == 0)
2250 			break;
2251 
2252 		/*
2253 		 * Calculate time spent sitting on run queue
2254 		 */
2255 		now = gethrtime_unscaled();
2256 		rqtime = now - tp->t_waitrq;
2257 		scalehrtime(&rqtime);
2258 
2259 		/*
2260 		 * Steal immediately if the time spent on this run queue is more
2261 		 * than allowed nosteal delay.
2262 		 *
2263 		 * Negative rqtime check is needed here to avoid infinite
2264 		 * stealing delays caused by unlikely but not impossible
2265 		 * drifts between CPU times on different CPUs.
2266 		 */
2267 		if (rqtime > nosteal || rqtime < 0)
2268 			break;
2269 
2270 		DTRACE_PROBE4(nosteal, kthread_t *, tp,
2271 		    cpu_t *, tcp, cpu_t *, cp, hrtime_t, rqtime);
2272 		scalehrtime(&now);
2273 		/*
2274 		 * Calculate when this thread becomes stealable
2275 		 */
2276 		now += (nosteal - rqtime);
2277 
2278 		/*
2279 		 * Calculate time when some thread becomes stealable
2280 		 */
2281 		if (now < dp->disp_steal)
2282 			dp->disp_steal = now;
2283 	}
2284 
2285 	/*
2286 	 * If there were no unbound threads on this queue, find the queue
2287 	 * where they are and then return later. The value of
2288 	 * disp_max_unbound_pri is not always accurate because it isn't
2289 	 * reduced until another idle CPU looks for work.
2290 	 */
2291 	if (allbound)
2292 		disp_fix_unbound_pri(dp, pri);
2293 
2294 	/*
2295 	 * If we reached the end of the queue and found no unbound threads
2296 	 * then return NULL so that other CPUs will be considered.  If there
2297 	 * are unbound threads but they cannot yet be stolen, then
2298 	 * return T_DONTSTEAL and try again later.
2299 	 */
2300 	if (tp == NULL) {
2301 		disp_lock_exit_nopreempt(&dp->disp_lock);
2302 		return (allbound ? NULL : T_DONTSTEAL);
2303 	}
2304 
2305 	/*
2306 	 * Found a runnable, unbound thread, so remove it from queue.
2307 	 * dispdeq() requires that we have the thread locked, and we do,
2308 	 * by virtue of holding the dispatch queue lock.  dispdeq() will
2309 	 * put the thread in transition state, thereby dropping the dispq
2310 	 * lock.
2311 	 */
2312 
2313 #ifdef DEBUG
2314 	{
2315 		int	thread_was_on_queue;
2316 
2317 		thread_was_on_queue = dispdeq(tp);	/* drops disp_lock */
2318 		ASSERT(thread_was_on_queue);
2319 	}
2320 
2321 #else /* DEBUG */
2322 	(void) dispdeq(tp);			/* drops disp_lock */
2323 #endif /* DEBUG */
2324 
2325 	/*
2326 	 * Reset the disp_queue steal time - we do not know what is the smallest
2327 	 * value across the queue is.
2328 	 */
2329 	dp->disp_steal = 0;
2330 
2331 	tp->t_schedflag |= TS_DONT_SWAP;
2332 
2333 	/*
2334 	 * Setup thread to run on the current CPU.
2335 	 */
2336 	tp->t_disp_queue = cp->cpu_disp;
2337 
2338 	cp->cpu_dispthread = tp;		/* protected by spl only */
2339 	cp->cpu_dispatch_pri = pri;
2340 	ASSERT(pri == DISP_PRIO(tp));
2341 
2342 	DTRACE_PROBE3(steal, kthread_t *, tp, cpu_t *, tcp, cpu_t *, cp);
2343 
2344 	thread_onproc(tp, cp);			/* set t_state to TS_ONPROC */
2345 
2346 	/*
2347 	 * Return with spl high so that swtch() won't need to raise it.
2348 	 * The disp_lock was dropped by dispdeq().
2349 	 */
2350 
2351 	return (tp);
2352 }
2353 
2354 /*
2355  * disp_bound_common() - common routine for higher level functions
2356  *	that check for bound threads under certain conditions.
2357  *	If 'threadlistsafe' is set then there is no need to acquire
2358  *	pidlock to stop the thread list from changing (eg, if
2359  *	disp_bound_* is called with cpus paused).
2360  */
2361 static int
2362 disp_bound_common(cpu_t *cp, int threadlistsafe, int flag)
2363 {
2364 	int		found = 0;
2365 	kthread_t	*tp;
2366 
2367 	ASSERT(flag);
2368 
2369 	if (!threadlistsafe)
2370 		mutex_enter(&pidlock);
2371 	tp = curthread;		/* faster than allthreads */
2372 	do {
2373 		if (tp->t_state != TS_FREE) {
2374 			/*
2375 			 * If an interrupt thread is busy, but the
2376 			 * caller doesn't care (i.e. BOUND_INTR is off),
2377 			 * then just ignore it and continue through.
2378 			 */
2379 			if ((tp->t_flag & T_INTR_THREAD) &&
2380 			    !(flag & BOUND_INTR))
2381 				continue;
2382 
2383 			/*
2384 			 * Skip the idle thread for the CPU
2385 			 * we're about to set offline.
2386 			 */
2387 			if (tp == cp->cpu_idle_thread)
2388 				continue;
2389 
2390 			/*
2391 			 * Skip the pause thread for the CPU
2392 			 * we're about to set offline.
2393 			 */
2394 			if (tp == cp->cpu_pause_thread)
2395 				continue;
2396 
2397 			if ((flag & BOUND_CPU) &&
2398 			    (tp->t_bound_cpu == cp ||
2399 			    tp->t_bind_cpu == cp->cpu_id ||
2400 			    tp->t_weakbound_cpu == cp)) {
2401 				found = 1;
2402 				break;
2403 			}
2404 
2405 			if ((flag & BOUND_PARTITION) &&
2406 			    (tp->t_cpupart == cp->cpu_part)) {
2407 				found = 1;
2408 				break;
2409 			}
2410 		}
2411 	} while ((tp = tp->t_next) != curthread && found == 0);
2412 	if (!threadlistsafe)
2413 		mutex_exit(&pidlock);
2414 	return (found);
2415 }
2416 
2417 /*
2418  * disp_bound_threads - return nonzero if threads are bound to the processor.
2419  *	Called infrequently.  Keep this simple.
2420  *	Includes threads that are asleep or stopped but not onproc.
2421  */
2422 int
2423 disp_bound_threads(cpu_t *cp, int threadlistsafe)
2424 {
2425 	return (disp_bound_common(cp, threadlistsafe, BOUND_CPU));
2426 }
2427 
2428 /*
2429  * disp_bound_anythreads - return nonzero if _any_ threads are bound
2430  * to the given processor, including interrupt threads.
2431  */
2432 int
2433 disp_bound_anythreads(cpu_t *cp, int threadlistsafe)
2434 {
2435 	return (disp_bound_common(cp, threadlistsafe, BOUND_CPU | BOUND_INTR));
2436 }
2437 
2438 /*
2439  * disp_bound_partition - return nonzero if threads are bound to the same
2440  * partition as the processor.
2441  *	Called infrequently.  Keep this simple.
2442  *	Includes threads that are asleep or stopped but not onproc.
2443  */
2444 int
2445 disp_bound_partition(cpu_t *cp, int threadlistsafe)
2446 {
2447 	return (disp_bound_common(cp, threadlistsafe, BOUND_PARTITION));
2448 }
2449 
2450 /*
2451  * disp_cpu_inactive - make a CPU inactive by moving all of its unbound
2452  * threads to other CPUs.
2453  */
2454 void
2455 disp_cpu_inactive(cpu_t *cp)
2456 {
2457 	kthread_t	*tp;
2458 	disp_t		*dp = cp->cpu_disp;
2459 	dispq_t		*dq;
2460 	pri_t		pri;
2461 	int		wasonq;
2462 
2463 	disp_lock_enter(&dp->disp_lock);
2464 	while ((pri = dp->disp_max_unbound_pri) != -1) {
2465 		dq = &dp->disp_q[pri];
2466 		tp = dq->dq_first;
2467 
2468 		/*
2469 		 * Skip over bound threads.
2470 		 */
2471 		while (tp != NULL && tp->t_bound_cpu != NULL) {
2472 			tp = tp->t_link;
2473 		}
2474 
2475 		if (tp == NULL) {
2476 			/* disp_max_unbound_pri must be inaccurate, so fix it */
2477 			disp_fix_unbound_pri(dp, pri);
2478 			continue;
2479 		}
2480 
2481 		wasonq = dispdeq(tp);		/* drops disp_lock */
2482 		ASSERT(wasonq);
2483 		ASSERT(tp->t_weakbound_cpu == NULL);
2484 
2485 		setbackdq(tp);
2486 		/*
2487 		 * Called from cpu_offline:
2488 		 *
2489 		 * cp has already been removed from the list of active cpus
2490 		 * and tp->t_cpu has been changed so there is no risk of
2491 		 * tp ending up back on cp.
2492 		 *
2493 		 * Called from cpupart_move_cpu:
2494 		 *
2495 		 * The cpu has moved to a new cpupart.  Any threads that
2496 		 * were on it's dispatch queues before the move remain
2497 		 * in the old partition and can't run in the new partition.
2498 		 */
2499 		ASSERT(tp->t_cpu != cp);
2500 		thread_unlock(tp);
2501 
2502 		disp_lock_enter(&dp->disp_lock);
2503 	}
2504 	disp_lock_exit(&dp->disp_lock);
2505 }
2506 
2507 /*
2508  * disp_lowpri_cpu - find CPU running the lowest priority thread.
2509  *	The hint passed in is used as a starting point so we don't favor
2510  *	CPU 0 or any other CPU.  The caller should pass in the most recently
2511  *	used CPU for the thread.
2512  *
2513  *	The lgroup and priority are used to determine the best CPU to run on
2514  *	in a NUMA machine.  The lgroup specifies which CPUs are closest while
2515  *	the thread priority will indicate whether the thread will actually run
2516  *	there.  To pick the best CPU, the CPUs inside and outside of the given
2517  *	lgroup which are running the lowest priority threads are found.  The
2518  *	remote CPU is chosen only if the thread will not run locally on a CPU
2519  *	within the lgroup, but will run on the remote CPU. If the thread
2520  *	cannot immediately run on any CPU, the best local CPU will be chosen.
2521  *
2522  *	The lpl specified also identifies the cpu partition from which
2523  *	disp_lowpri_cpu should select a CPU.
2524  *
2525  *	curcpu is used to indicate that disp_lowpri_cpu is being called on
2526  *      behalf of the current thread. (curthread is looking for a new cpu)
2527  *      In this case, cpu_dispatch_pri for this thread's cpu should be
2528  *      ignored.
2529  *
2530  *      If a cpu is the target of an offline request then try to avoid it.
2531  *
2532  *	This function must be called at either high SPL, or with preemption
2533  *	disabled, so that the "hint" CPU cannot be removed from the online
2534  *	CPU list while we are traversing it.
2535  */
2536 cpu_t *
2537 disp_lowpri_cpu(cpu_t *hint, lpl_t *lpl, pri_t tpri, cpu_t *curcpu)
2538 {
2539 	cpu_t	*bestcpu;
2540 	cpu_t	*besthomecpu;
2541 	cpu_t   *cp, *cpstart;
2542 
2543 	pri_t   bestpri;
2544 	pri_t   cpupri;
2545 
2546 	klgrpset_t	done;
2547 	klgrpset_t	cur_set;
2548 
2549 	lpl_t		*lpl_iter, *lpl_leaf;
2550 	int		i;
2551 
2552 	/*
2553 	 * Scan for a CPU currently running the lowest priority thread.
2554 	 * Cannot get cpu_lock here because it is adaptive.
2555 	 * We do not require lock on CPU list.
2556 	 */
2557 	ASSERT(hint != NULL);
2558 	ASSERT(lpl != NULL);
2559 	ASSERT(lpl->lpl_ncpu > 0);
2560 
2561 	/*
2562 	 * First examine local CPUs. Note that it's possible the hint CPU
2563 	 * passed in in remote to the specified home lgroup. If our priority
2564 	 * isn't sufficient enough such that we can run immediately at home,
2565 	 * then examine CPUs remote to our home lgroup.
2566 	 * We would like to give preference to CPUs closest to "home".
2567 	 * If we can't find a CPU where we'll run at a given level
2568 	 * of locality, we expand our search to include the next level.
2569 	 */
2570 	bestcpu = besthomecpu = NULL;
2571 	klgrpset_clear(done);
2572 	/* start with lpl we were passed */
2573 
2574 	lpl_iter = lpl;
2575 
2576 	do {
2577 
2578 		bestpri = SHRT_MAX;
2579 		klgrpset_clear(cur_set);
2580 
2581 		for (i = 0; i < lpl_iter->lpl_nrset; i++) {
2582 			lpl_leaf = lpl_iter->lpl_rset[i];
2583 			if (klgrpset_ismember(done, lpl_leaf->lpl_lgrpid))
2584 				continue;
2585 
2586 			klgrpset_add(cur_set, lpl_leaf->lpl_lgrpid);
2587 
2588 			if (hint->cpu_lpl == lpl_leaf)
2589 				cp = cpstart = hint;
2590 			else
2591 				cp = cpstart = lpl_leaf->lpl_cpus;
2592 
2593 			do {
2594 				if (cp == curcpu)
2595 					cpupri = -1;
2596 				else if (cp == cpu_inmotion)
2597 					cpupri = SHRT_MAX;
2598 				else
2599 					cpupri = cp->cpu_dispatch_pri;
2600 				if (cp->cpu_disp->disp_maxrunpri > cpupri)
2601 					cpupri = cp->cpu_disp->disp_maxrunpri;
2602 				if (cp->cpu_chosen_level > cpupri)
2603 					cpupri = cp->cpu_chosen_level;
2604 				if (cpupri < bestpri) {
2605 					if (CPU_IDLING(cpupri)) {
2606 						ASSERT((cp->cpu_flags &
2607 						    CPU_QUIESCED) == 0);
2608 						return (cp);
2609 					}
2610 					bestcpu = cp;
2611 					bestpri = cpupri;
2612 				}
2613 			} while ((cp = cp->cpu_next_lpl) != cpstart);
2614 		}
2615 
2616 		if (bestcpu && (tpri > bestpri)) {
2617 			ASSERT((bestcpu->cpu_flags & CPU_QUIESCED) == 0);
2618 			return (bestcpu);
2619 		}
2620 		if (besthomecpu == NULL)
2621 			besthomecpu = bestcpu;
2622 		/*
2623 		 * Add the lgrps we just considered to the "done" set
2624 		 */
2625 		klgrpset_or(done, cur_set);
2626 
2627 	} while ((lpl_iter = lpl_iter->lpl_parent) != NULL);
2628 
2629 	/*
2630 	 * The specified priority isn't high enough to run immediately
2631 	 * anywhere, so just return the best CPU from the home lgroup.
2632 	 */
2633 	ASSERT((besthomecpu->cpu_flags & CPU_QUIESCED) == 0);
2634 	return (besthomecpu);
2635 }
2636 
2637 /*
2638  * This routine provides the generic idle cpu function for all processors.
2639  * If a processor has some specific code to execute when idle (say, to stop
2640  * the pipeline and save power) then that routine should be defined in the
2641  * processors specific code (module_xx.c) and the global variable idle_cpu
2642  * set to that function.
2643  */
2644 static void
2645 generic_idle_cpu(void)
2646 {
2647 }
2648 
2649 /*ARGSUSED*/
2650 static void
2651 generic_enq_thread(cpu_t *cpu, int bound)
2652 {
2653 }
2654 
2655 /*
2656  * Select a CPU for this thread to run on.  Choose t->t_cpu unless:
2657  *	- t->t_cpu is not in this thread's assigned lgrp
2658  *	- the time since the thread last came off t->t_cpu exceeds the
2659  *	  rechoose time for this cpu (ignore this if t is curthread in
2660  *	  which case it's on CPU and t->t_disp_time is inaccurate)
2661  *	- t->t_cpu is presently the target of an offline or partition move
2662  *	  request
2663  */
2664 static cpu_t *
2665 cpu_choose(kthread_t *t, pri_t tpri)
2666 {
2667 	ASSERT(tpri < kpqpri);
2668 
2669 	if ((((lbolt - t->t_disp_time) > rechoose_interval) &&
2670 	    t != curthread) || t->t_cpu == cpu_inmotion) {
2671 		return (disp_lowpri_cpu(t->t_cpu, t->t_lpl, tpri, NULL));
2672 	}
2673 
2674 	/*
2675 	 * Take a trip through disp_lowpri_cpu() if the thread was
2676 	 * running outside it's home lgroup
2677 	 */
2678 	if (!klgrpset_ismember(t->t_lpl->lpl_lgrp->lgrp_set[LGRP_RSRC_CPU],
2679 	    t->t_cpu->cpu_lpl->lpl_lgrpid)) {
2680 		return (disp_lowpri_cpu(t->t_cpu, t->t_lpl, tpri,
2681 		    (t == curthread) ? t->t_cpu : NULL));
2682 	}
2683 	return (t->t_cpu);
2684 }
2685