kern_switch.c revision 104695
1/*
2 * Copyright (c) 2001 Jake Burkholder <jake@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, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD: head/sys/kern/kern_switch.c 104695 2002-10-09 02:33:36Z julian $
27 */
28
29/***
30
31Here is the logic..
32
33If there are N processors, then there are at most N KSEs (kernel
34schedulable entities) working to process threads that belong to a
35KSEGOUP (kg). If there are X of these KSEs actually running at the
36moment in question, then there are at most M (N-X) of these KSEs on
37the run queue, as running KSEs are not on the queue.
38
39Runnable threads are queued off the KSEGROUP in priority order.
40If there are M or more threads runnable, the top M threads
41(by priority) are 'preassigned' to the M KSEs not running. The KSEs take
42their priority from those threads and are put on the run queue.
43
44The last thread that had a priority high enough to have a KSE associated
45with it, AND IS ON THE RUN QUEUE is pointed to by
46kg->kg_last_assigned. If no threads queued off the KSEGROUP have KSEs
47assigned as all the available KSEs are activly running, or because there
48are no threads queued, that pointer is NULL.
49
50When a KSE is removed from the run queue to become runnable, we know
51it was associated with the highest priority thread in the queue (at the head
52of the queue). If it is also the last assigned we know M was 1 and must
53now be 0. Since the thread is no longer queued that pointer must be
54removed from it. Since we know there were no more KSEs available,
55(M was 1 and is now 0) and since we are not FREEING our KSE
56but using it, we know there are STILL no more KSEs available, we can prove
57that the next thread in the ksegrp list will not have a KSE to assign to
58it, so we can show that the pointer must be made 'invalid' (NULL).
59
60The pointer exists so that when a new thread is made runnable, it can
61have its priority compared with the last assigned thread to see if
62it should 'steal' its KSE or not.. i.e. is it 'earlier'
63on the list than that thread or later.. If it's earlier, then the KSE is
64removed from the last assigned (which is now not assigned a KSE)
65and reassigned to the new thread, which is placed earlier in the list.
66The pointer is then backed up to the previous thread (which may or may not
67be the new thread).
68
69When a thread sleeps or is removed, the KSE becomes available and if there
70are queued threads that are not assigned KSEs, the highest priority one of
71them is assigned the KSE, which is then placed back on the run queue at
72the approipriate place, and the kg->kg_last_assigned pointer is adjusted down
73to point to it.
74
75The following diagram shows 2 KSEs and 3 threads from a single process.
76
77 RUNQ: --->KSE---KSE--...    (KSEs queued at priorities from threads)
78              \    \____
79               \        \
80    KSEGROUP---thread--thread--thread    (queued in priority order)
81        \                 /
82         \_______________/
83          (last_assigned)
84
85The result of this scheme is that the M available KSEs are always
86queued at the priorities they have inherrited from the M highest priority
87threads for that KSEGROUP. If this situation changes, the KSEs are
88reassigned to keep this true.
89
90*/
91
92#include <sys/param.h>
93#include <sys/systm.h>
94#include <sys/kernel.h>
95#include <sys/ktr.h>
96#include <sys/lock.h>
97#include <sys/mutex.h>
98#include <sys/proc.h>
99#include <sys/queue.h>
100#include <machine/critical.h>
101
102CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS);
103
104/*
105 * Global run queue.
106 */
107static struct runq runq;
108SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq)
109
110void panc(char *string1, char *string2);
111
112#if 0
113static void runq_readjust(struct runq *rq, struct kse *ke);
114#endif
115/************************************************************************
116 * Functions that manipulate runnability from a thread perspective.	*
117 ************************************************************************/
118
119/*
120 * Select the KSE that will be run next.  From that find the thread, and x
121 * remove it from the KSEGRP's run queue.  If there is thread clustering,
122 * this will be what does it.
123 */
124struct thread *
125choosethread(void)
126{
127	struct kse *ke;
128	struct thread *td;
129	struct ksegrp *kg;
130
131retry:
132	if ((ke = runq_choose(&runq))) {
133		td = ke->ke_thread;
134		KASSERT((td->td_kse == ke), ("kse/thread mismatch"));
135		kg = ke->ke_ksegrp;
136		if (td->td_flags & TDF_UNBOUND) {
137			TAILQ_REMOVE(&kg->kg_runq, td, td_runq);
138			if (kg->kg_last_assigned == td) {
139				if (TAILQ_PREV(td, threadqueue, td_runq)
140				    != NULL)
141					printf("Yo MAMA!\n");
142				kg->kg_last_assigned = TAILQ_PREV(td,
143				    threadqueue, td_runq);
144			}
145			/*
146			 *  If we have started running an upcall,
147			 * Then TDF_UNBOUND WAS set because the thread was
148			 * created without a KSE. Now that we have one,
149			 * and it is our time to run, we make sure
150			 * that BOUND semantics apply for the rest of
151			 * the journey to userland, and into the UTS.
152			 */
153#ifdef	NOTYET
154			if (td->td_flags & TDF_UPCALLING)
155				tdf->td_flags &= ~TDF_UNBOUND;
156#endif
157		}
158		kg->kg_runnable--;
159		CTR2(KTR_RUNQ, "choosethread: td=%p pri=%d",
160		    td, td->td_priority);
161	} else {
162		/* Simulate runq_choose() having returned the idle thread */
163		td = PCPU_GET(idlethread);
164		ke = td->td_kse;
165		CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td);
166	}
167	ke->ke_flags |= KEF_DIDRUN;
168	if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 &&
169	    (td->td_flags & TDF_INPANIC) == 0))
170		goto retry;
171	TD_SET_RUNNING(td);
172	return (td);
173}
174
175/*
176 * Given a KSE (now surplus or at least loanable), either assign a new
177 * runable thread to it
178 * (and put it in the run queue) or put it in the ksegrp's idle KSE list.
179 * Or aybe give it back to its owner if it's been loaned.
180 */
181void
182kse_reassign(struct kse *ke)
183{
184	struct ksegrp *kg;
185	struct thread *td;
186	struct thread *owner;
187	struct thread *original;
188
189	mtx_assert(&sched_lock, MA_OWNED);
190	kg = ke->ke_ksegrp;
191	owner = ke->ke_bound;
192	original = ke->ke_thread;
193	KASSERT(!(owner && ((owner->td_kse != ke) ||
194		    (owner->td_flags & TDF_UNBOUND))),
195		("kse_reassign: bad thread bound state"));
196
197	/*
198	 * Find the first unassigned thread
199	 * If there is a 'last assigned' then see what's next.
200	 * otherwise look at what is first.
201	 */
202	if ((td = kg->kg_last_assigned)) {
203		td = TAILQ_NEXT(td, td_runq);
204	} else {
205		td = TAILQ_FIRST(&kg->kg_runq);
206	}
207
208	/*
209	 * If we found one assign it the kse, otherwise idle the kse.
210	 */
211	if (td) {
212		/*
213		 * If the original is bound to us we can only be lent out so
214		 * make a loan, otherwise we just drop the
215		 * original thread.
216		 */
217		if (original) {
218			if (((original->td_flags & TDF_UNBOUND) == 0)) {
219				/*
220				 * Put the owner on the side
221				 */
222				ke->ke_bound = original;
223				TD_SET_LOAN(original);
224			} else {
225				original->td_kse = NULL;
226			}
227		}
228		kg->kg_last_assigned = td;
229		td->td_kse = ke;
230		ke->ke_thread = td;
231		runq_add(&runq, ke);
232		/*
233		 * if we have already borrowed this,
234		 * just pass it to the new thread,
235		 * otherwise, enact the loan.
236		 */
237		CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p", ke, td);
238		return;
239	}
240	if (owner) { /* already loaned out */
241		/* effectivly unloan it */
242		TD_CLR_LOAN(owner);
243		ke->ke_thread = owner;
244		ke->ke_bound = NULL;
245		if (original)
246			original->td_kse = NULL;
247		original = owner;
248
249		if (TD_CAN_RUN(owner)) {
250			/*
251			 * If the owner thread is now runnable,  run it..
252			 * Let it have its KSE back.
253			 */
254			setrunqueue(owner);
255			CTR2(KTR_RUNQ, "kse_reassign: ke%p -> td%p (give back)",
256			    ke, owner);
257			return;
258		}
259	}
260	/*
261	 * Presetly NOT loaned out.
262	 * If we are bound, we go on the loanable queue
263	 * otherwise onto the free queue.
264	 */
265	if (original) {
266		if (((original->td_flags & TDF_UNBOUND) == 0)) {
267			ke->ke_state = KES_THREAD;
268			ke->ke_flags |= KEF_ONLOANQ;
269			ke->ke_bound = NULL;
270			TAILQ_INSERT_HEAD(&kg->kg_lq, ke, ke_kgrlist);
271			kg->kg_loan_kses++;
272			CTR1(KTR_RUNQ, "kse_reassign: ke%p on loan queue", ke);
273			return;
274		} else {
275			original->td_kse = NULL;
276		}
277	}
278	ke->ke_state = KES_IDLE;
279	ke->ke_thread = NULL;
280	TAILQ_INSERT_HEAD(&kg->kg_iq, ke, ke_kgrlist);
281	kg->kg_idle_kses++;
282	CTR1(KTR_RUNQ, "kse_reassign: ke%p idled", ke);
283}
284
285int
286kserunnable(void)
287{
288	return runq_check(&runq);
289}
290
291/*
292 * Remove a thread from its KSEGRP's run queue.
293 * This in turn may remove it from a KSE if it was already assigned
294 * to one, possibly causing a new thread to be assigned to the KSE
295 * and the KSE getting a new priority (unless it's a BOUND thread/KSE pair).
296 */
297void
298remrunqueue(struct thread *td)
299{
300	struct thread *td2, *td3;
301	struct ksegrp *kg;
302	struct kse *ke;
303
304	mtx_assert(&sched_lock, MA_OWNED);
305	KASSERT ((TD_ON_RUNQ(td)), ("remrunqueue: Bad state on run queue"));
306	kg = td->td_ksegrp;
307	ke = td->td_kse;
308	/*
309	 * If it's a bound thread/KSE pair, take the shortcut. All non-KSE
310	 * threads are BOUND.
311	 */
312	CTR1(KTR_RUNQ, "remrunqueue: td%p", td);
313	kg->kg_runnable--;
314	TD_SET_CAN_RUN(td);
315	if ((td->td_flags & TDF_UNBOUND) == 0)  {
316		/* Bring its kse with it, leave the thread attached */
317		runq_remove(&runq, ke);
318		ke->ke_state = KES_THREAD;
319		return;
320	}
321   	td3 = TAILQ_PREV(td, threadqueue, td_runq);
322	TAILQ_REMOVE(&kg->kg_runq, td, td_runq);
323	if (ke) {
324		/*
325		 * This thread has been assigned to a KSE.
326		 * We need to dissociate it and try assign the
327		 * KSE to the next available thread. Then, we should
328		 * see if we need to move the KSE in the run queues.
329		 */
330		td2 = kg->kg_last_assigned;
331		KASSERT((td2 != NULL), ("last assigned has wrong value "));
332		if (td2 == td)
333			kg->kg_last_assigned = td3;
334		td->td_kse = NULL;
335		ke->ke_thread = NULL;
336		kse_reassign(ke);
337	}
338}
339
340void
341setrunqueue(struct thread *td)
342{
343	struct kse *ke;
344	struct ksegrp *kg;
345	struct thread *td2;
346	struct thread *tda;
347
348	CTR1(KTR_RUNQ, "setrunqueue: td%p", td);
349	mtx_assert(&sched_lock, MA_OWNED);
350	KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
351	    ("setrunqueue: bad thread state"));
352	TD_SET_RUNQ(td);
353	kg = td->td_ksegrp;
354	kg->kg_runnable++;
355	if ((td->td_proc->p_flag & P_KSES) == 0) {
356		/*
357		 * Common path optimisation: Only one of everything
358		 * and the KSE is always already attached.
359		 * Totally ignore the ksegrp run queue.
360		 */
361		runq_add(&runq, td->td_kse);
362		return;
363	}
364	if ((td->td_flags & TDF_UNBOUND) == 0) {
365		KASSERT((td->td_kse != NULL),
366		    ("queueing BAD thread to run queue"));
367		ke = td->td_kse;
368		ke->ke_bound = NULL;
369		if (ke->ke_flags & KEF_ONLOANQ) {
370			ke->ke_flags &= ~KEF_ONLOANQ;
371			TAILQ_REMOVE(&kg->kg_lq, ke, ke_kgrlist);
372			kg->kg_loan_kses--;
373		}
374		runq_add(&runq, td->td_kse);
375		return;
376	}
377
378	/*
379	 * Ok, so we are threading with this thread.
380	 * We don't have a KSE, see if we can get one..
381	 */
382	tda = kg->kg_last_assigned;
383	if ((ke = td->td_kse) == NULL) {
384		/*
385		 * We will need a KSE, see if there is one..
386		 * First look for a free one, before getting desperate.
387		 * If we can't get one, our priority is not high enough..
388		 * that's ok..
389		 */
390		if (kg->kg_idle_kses) {
391			/*
392			 * There is a free one so it's ours for the asking..
393			 */
394			ke = TAILQ_FIRST(&kg->kg_iq);
395			TAILQ_REMOVE(&kg->kg_iq, ke, ke_kgrlist);
396			ke->ke_state = KES_THREAD;
397			kg->kg_idle_kses--;
398		} else if (kg->kg_loan_kses) {
399			/*
400			 * Failing that see if we can borrow one.
401			 */
402			ke = TAILQ_FIRST(&kg->kg_lq);
403			TAILQ_REMOVE(&kg->kg_lq, ke, ke_kgrlist);
404			ke->ke_flags &= ~KEF_ONLOANQ;
405			ke->ke_state = KES_THREAD;
406			TD_SET_LOAN(ke->ke_thread);
407			ke->ke_bound = ke->ke_thread;
408			ke->ke_thread  = NULL;
409			kg->kg_loan_kses--;
410		} else if (tda && (tda->td_priority > td->td_priority)) {
411			/*
412			 * None free, but there is one we can commandeer.
413			 */
414			ke = tda->td_kse;
415			tda->td_kse = NULL;
416			ke->ke_thread = NULL;
417			tda = kg->kg_last_assigned =
418		    	    TAILQ_PREV(tda, threadqueue, td_runq);
419			runq_remove(&runq, ke);
420		}
421	} else {
422		/*
423		 * Temporarily disassociate so it looks like the other cases.
424		 */
425		ke->ke_thread = NULL;
426		td->td_kse = NULL;
427	}
428
429	/*
430	 * Add the thread to the ksegrp's run queue at
431	 * the appropriate place.
432	 */
433	TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) {
434		if (td2->td_priority > td->td_priority) {
435			TAILQ_INSERT_BEFORE(td2, td, td_runq);
436			break;
437		}
438	}
439	if (td2 == NULL) {
440		/* We ran off the end of the TAILQ or it was empty. */
441		TAILQ_INSERT_TAIL(&kg->kg_runq, td, td_runq);
442	}
443
444	/*
445	 * If we have a ke to use, then put it on the run queue and
446	 * If needed, readjust the last_assigned pointer.
447	 */
448	if (ke) {
449		if (tda == NULL) {
450			/*
451			 * No pre-existing last assigned so whoever is first
452			 * gets the KSE we brought in.. (maybe us)
453			 */
454			td2 = TAILQ_FIRST(&kg->kg_runq);
455			KASSERT((td2->td_kse == NULL),
456			    ("unexpected ke present"));
457			td2->td_kse = ke;
458			ke->ke_thread = td2;
459			kg->kg_last_assigned = td2;
460		} else if (tda->td_priority > td->td_priority) {
461			/*
462			 * It's ours, grab it, but last_assigned is past us
463			 * so don't change it.
464			 */
465			td->td_kse = ke;
466			ke->ke_thread = td;
467		} else {
468			/*
469			 * We are past last_assigned, so
470			 * put the new kse on whatever is next,
471			 * which may or may not be us.
472			 */
473			td2 = TAILQ_NEXT(tda, td_runq);
474			kg->kg_last_assigned = td2;
475			td2->td_kse = ke;
476			ke->ke_thread = td2;
477		}
478		runq_add(&runq, ke);
479	}
480}
481
482/************************************************************************
483 * Critical section marker functions					*
484 ************************************************************************/
485/* Critical sections that prevent preemption. */
486void
487critical_enter(void)
488{
489	struct thread *td;
490
491	td = curthread;
492	if (td->td_critnest == 0)
493		cpu_critical_enter();
494	td->td_critnest++;
495}
496
497void
498critical_exit(void)
499{
500	struct thread *td;
501
502	td = curthread;
503	if (td->td_critnest == 1) {
504		td->td_critnest = 0;
505		cpu_critical_exit();
506	} else {
507		td->td_critnest--;
508	}
509}
510
511
512/************************************************************************
513 * SYSTEM RUN QUEUE manipulations and tests				*
514 ************************************************************************/
515/*
516 * Initialize a run structure.
517 */
518void
519runq_init(struct runq *rq)
520{
521	int i;
522
523	bzero(rq, sizeof *rq);
524	for (i = 0; i < RQ_NQS; i++)
525		TAILQ_INIT(&rq->rq_queues[i]);
526}
527
528/*
529 * Clear the status bit of the queue corresponding to priority level pri,
530 * indicating that it is empty.
531 */
532static __inline void
533runq_clrbit(struct runq *rq, int pri)
534{
535	struct rqbits *rqb;
536
537	rqb = &rq->rq_status;
538	CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
539	    rqb->rqb_bits[RQB_WORD(pri)],
540	    rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
541	    RQB_BIT(pri), RQB_WORD(pri));
542	rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
543}
544
545/*
546 * Find the index of the first non-empty run queue.  This is done by
547 * scanning the status bits, a set bit indicates a non-empty queue.
548 */
549static __inline int
550runq_findbit(struct runq *rq)
551{
552	struct rqbits *rqb;
553	int pri;
554	int i;
555
556	rqb = &rq->rq_status;
557	for (i = 0; i < RQB_LEN; i++)
558		if (rqb->rqb_bits[i]) {
559			pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW);
560			CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
561			    rqb->rqb_bits[i], i, pri);
562			return (pri);
563		}
564
565	return (-1);
566}
567
568/*
569 * Set the status bit of the queue corresponding to priority level pri,
570 * indicating that it is non-empty.
571 */
572static __inline void
573runq_setbit(struct runq *rq, int pri)
574{
575	struct rqbits *rqb;
576
577	rqb = &rq->rq_status;
578	CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
579	    rqb->rqb_bits[RQB_WORD(pri)],
580	    rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
581	    RQB_BIT(pri), RQB_WORD(pri));
582	rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
583}
584
585/*
586 * Add the KSE to the queue specified by its priority, and set the
587 * corresponding status bit.
588 */
589void
590runq_add(struct runq *rq, struct kse *ke)
591{
592	struct rqhead *rqh;
593	int pri;
594
595	mtx_assert(&sched_lock, MA_OWNED);
596	KASSERT((ke->ke_thread != NULL), ("runq_add: No thread on KSE"));
597	KASSERT((ke->ke_thread->td_kse != NULL),
598	    ("runq_add: No KSE on thread"));
599	KASSERT(ke->ke_state != KES_ONRUNQ,
600	    ("runq_add: kse %p (%s) already in run queue", ke,
601	    ke->ke_proc->p_comm));
602	KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
603		("runq_add: process swapped out"));
604	pri = ke->ke_thread->td_priority / RQ_PPQ;
605	ke->ke_rqindex = pri;
606	runq_setbit(rq, pri);
607	rqh = &rq->rq_queues[pri];
608	CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
609	    ke->ke_proc, ke->ke_thread->td_priority, pri, rqh);
610	TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
611	ke->ke_ksegrp->kg_runq_kses++;
612	ke->ke_state = KES_ONRUNQ;
613}
614
615/*
616 * Return true if there are runnable processes of any priority on the run
617 * queue, false otherwise.  Has no side effects, does not modify the run
618 * queue structure.
619 */
620int
621runq_check(struct runq *rq)
622{
623	struct rqbits *rqb;
624	int i;
625
626	rqb = &rq->rq_status;
627	for (i = 0; i < RQB_LEN; i++)
628		if (rqb->rqb_bits[i]) {
629			CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
630			    rqb->rqb_bits[i], i);
631			return (1);
632		}
633	CTR0(KTR_RUNQ, "runq_check: empty");
634
635	return (0);
636}
637
638/*
639 * Find and remove the highest priority process from the run queue.
640 * If there are no runnable processes, the per-cpu idle process is
641 * returned.  Will not return NULL under any circumstances.
642 */
643struct kse *
644runq_choose(struct runq *rq)
645{
646	struct rqhead *rqh;
647	struct kse *ke;
648	int pri;
649
650	mtx_assert(&sched_lock, MA_OWNED);
651	while ((pri = runq_findbit(rq)) != -1) {
652		rqh = &rq->rq_queues[pri];
653		ke = TAILQ_FIRST(rqh);
654		KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
655		CTR3(KTR_RUNQ,
656		    "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
657		TAILQ_REMOVE(rqh, ke, ke_procq);
658		ke->ke_ksegrp->kg_runq_kses--;
659		if (TAILQ_EMPTY(rqh)) {
660			CTR0(KTR_RUNQ, "runq_choose: empty");
661			runq_clrbit(rq, pri);
662		}
663
664		ke->ke_state = KES_THREAD;
665		KASSERT((ke->ke_thread != NULL),
666		    ("runq_choose: No thread on KSE"));
667		KASSERT((ke->ke_thread->td_kse != NULL),
668		    ("runq_choose: No KSE on thread"));
669		KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
670			("runq_choose: process swapped out"));
671		return (ke);
672	}
673	CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
674
675	return (NULL);
676}
677
678/*
679 * Remove the KSE from the queue specified by its priority, and clear the
680 * corresponding status bit if the queue becomes empty.
681 * Caller must set ke->ke_state afterwards.
682 */
683void
684runq_remove(struct runq *rq, struct kse *ke)
685{
686	struct rqhead *rqh;
687	int pri;
688
689	KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue"));
690	mtx_assert(&sched_lock, MA_OWNED);
691	KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
692		("runq_remove: process swapped out"));
693	pri = ke->ke_rqindex;
694	rqh = &rq->rq_queues[pri];
695	CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
696	    ke, ke->ke_thread->td_priority, pri, rqh);
697	KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
698	TAILQ_REMOVE(rqh, ke, ke_procq);
699	if (TAILQ_EMPTY(rqh)) {
700		CTR0(KTR_RUNQ, "runq_remove: empty");
701		runq_clrbit(rq, pri);
702	}
703	ke->ke_state = KES_THREAD;
704	ke->ke_ksegrp->kg_runq_kses--;
705}
706
707#if 0
708static void
709runq_readjust(struct runq *rq, struct kse *ke)
710{
711
712	if (ke->ke_rqindex != (ke->ke_thread->td_priority / RQ_PPQ)) {
713		runq_remove(rq, ke);
714		runq_add(rq, ke);
715	}
716}
717#endif
718
719#if 0
720void
721panc(char *string1, char *string2)
722{
723	printf("%s", string1);
724	Debugger(string2);
725}
726
727void
728thread_sanity_check(struct thread *td, char *string)
729{
730	struct proc *p;
731	struct ksegrp *kg;
732	struct kse *ke;
733	struct thread *td2 = NULL;
734	unsigned int prevpri;
735	int	saw_lastassigned = 0;
736	int unassigned = 0;
737	int assigned = 0;
738
739	p = td->td_proc;
740	kg = td->td_ksegrp;
741	ke = td->td_kse;
742
743
744	if (ke) {
745		if (p != ke->ke_proc) {
746			panc(string, "wrong proc");
747		}
748		if (ke->ke_thread != td) {
749			panc(string, "wrong thread");
750		}
751	}
752
753	if ((p->p_flag & P_KSES) == 0) {
754		if (ke == NULL) {
755			panc(string, "non KSE thread lost kse");
756		}
757	} else {
758		prevpri = 0;
759		saw_lastassigned = 0;
760		unassigned = 0;
761		assigned = 0;
762		TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) {
763			if (td2->td_priority < prevpri) {
764				panc(string, "thread runqueue unosorted");
765			}
766			if ((td2->td_state == TDS_RUNQ) &&
767			    td2->td_kse &&
768			    (td2->td_kse->ke_state != KES_ONRUNQ)) {
769				panc(string, "KSE wrong state");
770			}
771			prevpri = td2->td_priority;
772			if (td2->td_kse) {
773				assigned++;
774				if (unassigned) {
775					panc(string, "unassigned before assigned");
776				}
777 				if  (kg->kg_last_assigned == NULL) {
778					panc(string, "lastassigned corrupt");
779				}
780				if (saw_lastassigned) {
781					panc(string, "last assigned not last");
782				}
783				if (td2->td_kse->ke_thread != td2) {
784					panc(string, "mismatched kse/thread");
785				}
786			} else {
787				unassigned++;
788			}
789			if (td2 == kg->kg_last_assigned) {
790				saw_lastassigned = 1;
791				if (td2->td_kse == NULL) {
792					panc(string, "last assigned not assigned");
793				}
794			}
795		}
796		if (kg->kg_last_assigned && (saw_lastassigned == 0)) {
797			panc(string, "where on earth does lastassigned point?");
798		}
799		FOREACH_THREAD_IN_GROUP(kg, td2) {
800			if (((td2->td_flags & TDF_UNBOUND) == 0) &&
801			    (TD_ON_RUNQ(td2))) {
802				assigned++;
803				if (td2->td_kse == NULL) {
804					panc(string, "BOUND thread with no KSE");
805				}
806			}
807		}
808#if 0
809		if ((unassigned + assigned) != kg->kg_runnable) {
810			panc(string, "wrong number in runnable");
811		}
812#endif
813	}
814	if (assigned == 12345) {
815		printf("%p %p %p %p %p %d, %d",
816		    td, td2, ke, kg, p, assigned, saw_lastassigned);
817	}
818}
819#endif
820
821