xref: /freebsd/sys/kern/kern_switch.c (revision 549835052949aa0dafc1626ce6dc51e4505bbaae)
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 
27 /***
28 Here is the logic..
29 
30 If there are N processors, then there are at most N KSEs (kernel
31 schedulable entities) working to process threads that belong to a
32 KSEGROUP (kg). If there are X of these KSEs actually running at the
33 moment in question, then there are at most M (N-X) of these KSEs on
34 the run queue, as running KSEs are not on the queue.
35 
36 Runnable threads are queued off the KSEGROUP in priority order.
37 If there are M or more threads runnable, the top M threads
38 (by priority) are 'preassigned' to the M KSEs not running. The KSEs take
39 their priority from those threads and are put on the run queue.
40 
41 The last thread that had a priority high enough to have a KSE associated
42 with it, AND IS ON THE RUN QUEUE is pointed to by
43 kg->kg_last_assigned. If no threads queued off the KSEGROUP have KSEs
44 assigned as all the available KSEs are activly running, or because there
45 are no threads queued, that pointer is NULL.
46 
47 When a KSE is removed from the run queue to become runnable, we know
48 it was associated with the highest priority thread in the queue (at the head
49 of the queue). If it is also the last assigned we know M was 1 and must
50 now be 0. Since the thread is no longer queued that pointer must be
51 removed from it. Since we know there were no more KSEs available,
52 (M was 1 and is now 0) and since we are not FREEING our KSE
53 but using it, we know there are STILL no more KSEs available, we can prove
54 that the next thread in the ksegrp list will not have a KSE to assign to
55 it, so we can show that the pointer must be made 'invalid' (NULL).
56 
57 The pointer exists so that when a new thread is made runnable, it can
58 have its priority compared with the last assigned thread to see if
59 it should 'steal' its KSE or not.. i.e. is it 'earlier'
60 on the list than that thread or later.. If it's earlier, then the KSE is
61 removed from the last assigned (which is now not assigned a KSE)
62 and reassigned to the new thread, which is placed earlier in the list.
63 The pointer is then backed up to the previous thread (which may or may not
64 be the new thread).
65 
66 When a thread sleeps or is removed, the KSE becomes available and if there
67 are queued threads that are not assigned KSEs, the highest priority one of
68 them is assigned the KSE, which is then placed back on the run queue at
69 the approipriate place, and the kg->kg_last_assigned pointer is adjusted down
70 to point to it.
71 
72 The following diagram shows 2 KSEs and 3 threads from a single process.
73 
74  RUNQ: --->KSE---KSE--...    (KSEs queued at priorities from threads)
75               \    \____
76                \        \
77     KSEGROUP---thread--thread--thread    (queued in priority order)
78         \                 /
79          \_______________/
80           (last_assigned)
81 
82 The result of this scheme is that the M available KSEs are always
83 queued at the priorities they have inherrited from the M highest priority
84 threads for that KSEGROUP. If this situation changes, the KSEs are
85 reassigned to keep this true.
86 ***/
87 
88 #include <sys/cdefs.h>
89 __FBSDID("$FreeBSD$");
90 
91 #include "opt_sched.h"
92 
93 #ifndef KERN_SWITCH_INCLUDE
94 #include <sys/param.h>
95 #include <sys/systm.h>
96 #include <sys/kdb.h>
97 #include <sys/kernel.h>
98 #include <sys/ktr.h>
99 #include <sys/lock.h>
100 #include <sys/mutex.h>
101 #include <sys/proc.h>
102 #include <sys/queue.h>
103 #include <sys/sched.h>
104 #else  /* KERN_SWITCH_INCLUDE */
105 #if defined(SMP) && (defined(__i386__) || defined(__amd64__))
106 #include <sys/smp.h>
107 #endif
108 #include <machine/critical.h>
109 #if defined(SMP) && defined(SCHED_4BSD)
110 #include <sys/sysctl.h>
111 #endif
112 
113 #ifdef FULL_PREEMPTION
114 #ifndef PREEMPTION
115 #error "The FULL_PREEMPTION option requires the PREEMPTION option"
116 #endif
117 #endif
118 
119 CTASSERT((RQB_BPW * RQB_LEN) == RQ_NQS);
120 
121 #define td_kse td_sched
122 
123 /************************************************************************
124  * Functions that manipulate runnability from a thread perspective.	*
125  ************************************************************************/
126 /*
127  * Select the KSE that will be run next.  From that find the thread, and
128  * remove it from the KSEGRP's run queue.  If there is thread clustering,
129  * this will be what does it.
130  */
131 struct thread *
132 choosethread(void)
133 {
134 	struct kse *ke;
135 	struct thread *td;
136 	struct ksegrp *kg;
137 
138 #if defined(SMP) && (defined(__i386__) || defined(__amd64__))
139 	if (smp_active == 0 && PCPU_GET(cpuid) != 0) {
140 		/* Shutting down, run idlethread on AP's */
141 		td = PCPU_GET(idlethread);
142 		ke = td->td_kse;
143 		CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td);
144 		ke->ke_flags |= KEF_DIDRUN;
145 		TD_SET_RUNNING(td);
146 		return (td);
147 	}
148 #endif
149 
150 retry:
151 	ke = sched_choose();
152 	if (ke) {
153 		td = ke->ke_thread;
154 		KASSERT((td->td_kse == ke), ("kse/thread mismatch"));
155 		kg = ke->ke_ksegrp;
156 		if (td->td_proc->p_flag & P_HADTHREADS) {
157 			if (kg->kg_last_assigned == td) {
158 				kg->kg_last_assigned = TAILQ_PREV(td,
159 				    threadqueue, td_runq);
160 			}
161 			TAILQ_REMOVE(&kg->kg_runq, td, td_runq);
162 			kg->kg_runnable--;
163 		}
164 		CTR2(KTR_RUNQ, "choosethread: td=%p pri=%d",
165 		    td, td->td_priority);
166 	} else {
167 		/* Simulate runq_choose() having returned the idle thread */
168 		td = PCPU_GET(idlethread);
169 		ke = td->td_kse;
170 		CTR1(KTR_RUNQ, "choosethread: td=%p (idle)", td);
171 	}
172 	ke->ke_flags |= KEF_DIDRUN;
173 
174 	/*
175 	 * If we are in panic, only allow system threads,
176 	 * plus the one we are running in, to be run.
177 	 */
178 	if (panicstr && ((td->td_proc->p_flag & P_SYSTEM) == 0 &&
179 	    (td->td_flags & TDF_INPANIC) == 0)) {
180 		/* note that it is no longer on the run queue */
181 		TD_SET_CAN_RUN(td);
182 		goto retry;
183 	}
184 
185 	TD_SET_RUNNING(td);
186 	return (td);
187 }
188 
189 /*
190  * Given a surplus system slot, try assign a new runnable thread to it.
191  * Called from:
192  *  sched_thread_exit()  (local)
193  *  sched_switch()  (local)
194  *  sched_thread_exit()  (local)
195  *  remrunqueue()  (local) (commented out)
196  */
197 static void
198 slot_fill(struct ksegrp *kg)
199 {
200 	struct thread *td;
201 
202 	mtx_assert(&sched_lock, MA_OWNED);
203 	while (kg->kg_avail_opennings > 0) {
204 		/*
205 		 * Find the first unassigned thread
206 		 */
207 		if ((td = kg->kg_last_assigned) != NULL)
208 			td = TAILQ_NEXT(td, td_runq);
209 		else
210 			td = TAILQ_FIRST(&kg->kg_runq);
211 
212 		/*
213 		 * If we found one, send it to the system scheduler.
214 		 */
215 		if (td) {
216 			kg->kg_last_assigned = td;
217 			kg->kg_avail_opennings--;
218 			sched_add(td, SRQ_BORING);
219 			CTR2(KTR_RUNQ, "slot_fill: td%p -> kg%p", td, kg);
220 		} else {
221 			/* no threads to use up the slots. quit now */
222 			break;
223 		}
224 	}
225 }
226 
227 #if 0
228 /*
229  * Remove a thread from its KSEGRP's run queue.
230  * This in turn may remove it from a KSE if it was already assigned
231  * to one, possibly causing a new thread to be assigned to the KSE
232  * and the KSE getting a new priority.
233  */
234 static void
235 remrunqueue(struct thread *td)
236 {
237 	struct thread *td2, *td3;
238 	struct ksegrp *kg;
239 	struct kse *ke;
240 
241 	mtx_assert(&sched_lock, MA_OWNED);
242 	KASSERT((TD_ON_RUNQ(td)), ("remrunqueue: Bad state on run queue"));
243 	kg = td->td_ksegrp;
244 	ke = td->td_kse;
245 	CTR1(KTR_RUNQ, "remrunqueue: td%p", td);
246 	TD_SET_CAN_RUN(td);
247 	/*
248 	 * If it is not a threaded process, take the shortcut.
249 	 */
250 	if ((td->td_proc->p_flag & P_HADTHREADS) == 0) {
251 		/* Bring its kse with it, leave the thread attached */
252 		sched_rem(td);
253 		kg->kg_avail_opennings++;
254 		ke->ke_state = KES_THREAD;
255 		return;
256 	}
257    	td3 = TAILQ_PREV(td, threadqueue, td_runq);
258 	TAILQ_REMOVE(&kg->kg_runq, td, td_runq);
259 	kg->kg_runnable--;
260 	if (ke->ke_state == KES_ONRUNQ) {
261 		/*
262 		 * This thread has been assigned to a KSE.
263 		 * We need to dissociate it and try assign the
264 		 * KSE to the next available thread. Then, we should
265 		 * see if we need to move the KSE in the run queues.
266 		 */
267 		sched_rem(td);
268 		kg->kg_avail_opennings++;
269 		ke->ke_state = KES_THREAD;
270 		td2 = kg->kg_last_assigned;
271 		KASSERT((td2 != NULL), ("last assigned has wrong value"));
272 		if (td2 == td)
273 			kg->kg_last_assigned = td3;
274 		slot_fill(kg);
275 	}
276 }
277 #endif
278 
279 /*
280  * Change the priority of a thread that is on the run queue.
281  */
282 void
283 adjustrunqueue( struct thread *td, int newpri)
284 {
285 	struct ksegrp *kg;
286 	struct kse *ke;
287 
288 	mtx_assert(&sched_lock, MA_OWNED);
289 	KASSERT((TD_ON_RUNQ(td)), ("adjustrunqueue: Bad state on run queue"));
290 
291 	ke = td->td_kse;
292 	CTR1(KTR_RUNQ, "adjustrunqueue: td%p", td);
293 	/*
294 	 * If it is not a threaded process, take the shortcut.
295 	 */
296 	if ((td->td_proc->p_flag & P_HADTHREADS) == 0) {
297 		/* We only care about the kse in the run queue. */
298 		td->td_priority = newpri;
299 		if (ke->ke_rqindex != (newpri / RQ_PPQ)) {
300 			sched_rem(td);
301 			sched_add(td, SRQ_BORING);
302 		}
303 		return;
304 	}
305 
306 	/* It is a threaded process */
307 	kg = td->td_ksegrp;
308 	TD_SET_CAN_RUN(td);
309 	if (ke->ke_state == KES_ONRUNQ) {
310 		if (kg->kg_last_assigned == td) {
311 			kg->kg_last_assigned =
312 			    TAILQ_PREV(td, threadqueue, td_runq);
313 		}
314 		sched_rem(td);
315 		kg->kg_avail_opennings++;
316 	}
317 	TAILQ_REMOVE(&kg->kg_runq, td, td_runq);
318 	kg->kg_runnable--;
319 	td->td_priority = newpri;
320 	setrunqueue(td, SRQ_BORING);
321 }
322 int limitcount;
323 void
324 setrunqueue(struct thread *td, int flags)
325 {
326 	struct ksegrp *kg;
327 	struct thread *td2;
328 	struct thread *tda;
329 	int count;
330 
331 	CTR3(KTR_RUNQ, "setrunqueue: td:%p kg:%p pid:%d",
332 	    td, td->td_ksegrp, td->td_proc->p_pid);
333 	mtx_assert(&sched_lock, MA_OWNED);
334 	KASSERT((TD_CAN_RUN(td) || TD_IS_RUNNING(td)),
335 	    ("setrunqueue: bad thread state"));
336 	TD_SET_RUNQ(td);
337 	kg = td->td_ksegrp;
338 	if ((td->td_proc->p_flag & P_HADTHREADS) == 0) {
339 		/*
340 		 * Common path optimisation: Only one of everything
341 		 * and the KSE is always already attached.
342 		 * Totally ignore the ksegrp run queue.
343 		 */
344 		if (kg->kg_avail_opennings != 1) {
345 			if (limitcount < 1) {
346 				limitcount++;
347 				printf("pid %d: corrected slot count (%d->1)\n",
348 				    td->td_proc->p_pid, kg->kg_avail_opennings);
349 
350 			}
351 			kg->kg_avail_opennings = 1;
352 		}
353 		kg->kg_avail_opennings--;
354 		sched_add(td, flags);
355 		return;
356 	}
357 
358 	tda = kg->kg_last_assigned;
359 	if ((kg->kg_avail_opennings <= 0) &&
360 	(tda && (tda->td_priority > td->td_priority))) {
361 		/*
362 		 * None free, but there is one we can commandeer.
363 		 */
364 		CTR2(KTR_RUNQ,
365 		    "setrunqueue: kg:%p: take slot from td: %p", kg, tda);
366 		sched_rem(tda);
367 		tda = kg->kg_last_assigned =
368 		    TAILQ_PREV(tda, threadqueue, td_runq);
369 		kg->kg_avail_opennings++;
370 	}
371 
372 	/*
373 	 * Add the thread to the ksegrp's run queue at
374 	 * the appropriate place.
375 	 */
376 	count = 0;
377 	TAILQ_FOREACH(td2, &kg->kg_runq, td_runq) {
378 		if (td2->td_priority > td->td_priority) {
379 			kg->kg_runnable++;
380 			TAILQ_INSERT_BEFORE(td2, td, td_runq);
381 			break;
382 		}
383 		/* XXX Debugging hack */
384 		if (++count > 10000) {
385 			printf("setrunqueue(): corrupt kq_runq, td= %p\n", td);
386 			panic("deadlock in setrunqueue");
387 		}
388 	}
389 	if (td2 == NULL) {
390 		/* We ran off the end of the TAILQ or it was empty. */
391 		kg->kg_runnable++;
392 		TAILQ_INSERT_TAIL(&kg->kg_runq, td, td_runq);
393 	}
394 
395 	/*
396 	 * If we have a slot to use, then put the thread on the system
397 	 * run queue and if needed, readjust the last_assigned pointer.
398 	 */
399 	if (kg->kg_avail_opennings > 0) {
400 		if (tda == NULL) {
401 			/*
402 			 * No pre-existing last assigned so whoever is first
403 			 * gets the KSE we brought in.. (maybe us)
404 			 */
405 			td2 = TAILQ_FIRST(&kg->kg_runq);
406 			kg->kg_last_assigned = td2;
407 		} else if (tda->td_priority > td->td_priority) {
408 			td2 = td;
409 		} else {
410 			/*
411 			 * We are past last_assigned, so
412 			 * gave the next slot to whatever is next,
413 			 * which may or may not be us.
414 			 */
415 			td2 = TAILQ_NEXT(tda, td_runq);
416 			kg->kg_last_assigned = td2;
417 		}
418 		kg->kg_avail_opennings--;
419 		sched_add(td2, flags);
420 	} else {
421 		CTR3(KTR_RUNQ, "setrunqueue: held: td%p kg%p pid%d",
422 			td, td->td_ksegrp, td->td_proc->p_pid);
423 	}
424 }
425 
426 /*
427  * Kernel thread preemption implementation.  Critical sections mark
428  * regions of code in which preemptions are not allowed.
429  */
430 void
431 critical_enter(void)
432 {
433 	struct thread *td;
434 
435 	td = curthread;
436 	if (td->td_critnest == 0)
437 		cpu_critical_enter(td);
438 	td->td_critnest++;
439 }
440 
441 void
442 critical_exit(void)
443 {
444 	struct thread *td;
445 
446 	td = curthread;
447 	KASSERT(td->td_critnest != 0,
448 	    ("critical_exit: td_critnest == 0"));
449 	if (td->td_critnest == 1) {
450 #ifdef PREEMPTION
451 		mtx_assert(&sched_lock, MA_NOTOWNED);
452 		if (td->td_pflags & TDP_OWEPREEMPT) {
453 			mtx_lock_spin(&sched_lock);
454 			mi_switch(SW_INVOL, NULL);
455 			mtx_unlock_spin(&sched_lock);
456 		}
457 #endif
458 		td->td_critnest = 0;
459 		cpu_critical_exit(td);
460 	} else {
461 		td->td_critnest--;
462 	}
463 }
464 
465 /*
466  * This function is called when a thread is about to be put on run queue
467  * because it has been made runnable or its priority has been adjusted.  It
468  * determines if the new thread should be immediately preempted to.  If so,
469  * it switches to it and eventually returns true.  If not, it returns false
470  * so that the caller may place the thread on an appropriate run queue.
471  */
472 int
473 maybe_preempt(struct thread *td)
474 {
475 #ifdef PREEMPTION
476 	struct thread *ctd;
477 	int cpri, pri;
478 #endif
479 
480 	mtx_assert(&sched_lock, MA_OWNED);
481 #ifdef PREEMPTION
482 	/*
483 	 * The new thread should not preempt the current thread if any of the
484 	 * following conditions are true:
485 	 *
486 	 *  - The current thread has a higher (numerically lower) or
487 	 *    equivalent priority.  Note that this prevents curthread from
488 	 *    trying to preempt to itself.
489 	 *  - It is too early in the boot for context switches (cold is set).
490 	 *  - The current thread has an inhibitor set or is in the process of
491 	 *    exiting.  In this case, the current thread is about to switch
492 	 *    out anyways, so there's no point in preempting.  If we did,
493 	 *    the current thread would not be properly resumed as well, so
494 	 *    just avoid that whole landmine.
495 	 *  - If the new thread's priority is not a realtime priority and
496 	 *    the current thread's priority is not an idle priority and
497 	 *    FULL_PREEMPTION is disabled.
498 	 *
499 	 * If all of these conditions are false, but the current thread is in
500 	 * a nested critical section, then we have to defer the preemption
501 	 * until we exit the critical section.  Otherwise, switch immediately
502 	 * to the new thread.
503 	 */
504 	ctd = curthread;
505 	KASSERT ((ctd->td_kse != NULL && ctd->td_kse->ke_thread == ctd),
506 	  ("thread has no (or wrong) sched-private part."));
507 	pri = td->td_priority;
508 	cpri = ctd->td_priority;
509 	if (pri >= cpri || cold /* || dumping */ || TD_IS_INHIBITED(ctd) ||
510 	    td->td_kse->ke_state != KES_THREAD)
511 		return (0);
512 #ifndef FULL_PREEMPTION
513 	if (!(pri >= PRI_MIN_ITHD && pri <= PRI_MAX_ITHD) &&
514 	    !(cpri >= PRI_MIN_IDLE))
515 		return (0);
516 #endif
517 	if (ctd->td_critnest > 1) {
518 		CTR1(KTR_PROC, "maybe_preempt: in critical section %d",
519 		    ctd->td_critnest);
520 		ctd->td_pflags |= TDP_OWEPREEMPT;
521 		return (0);
522 	}
523 
524 	/*
525 	 * Our thread state says that we are already on a run queue, so
526 	 * update our state as if we had been dequeued by choosethread().
527 	 */
528 	MPASS(TD_ON_RUNQ(td));
529 	TD_SET_RUNNING(td);
530 	CTR3(KTR_PROC, "preempting to thread %p (pid %d, %s)\n", td,
531 	    td->td_proc->p_pid, td->td_proc->p_comm);
532 	mi_switch(SW_INVOL, td);
533 	return (1);
534 #else
535 	return (0);
536 #endif
537 }
538 
539 #if 0
540 #ifndef PREEMPTION
541 /* XXX: There should be a non-static version of this. */
542 static void
543 printf_caddr_t(void *data)
544 {
545 	printf("%s", (char *)data);
546 }
547 static char preempt_warning[] =
548     "WARNING: Kernel preemption is disabled, expect reduced performance.\n";
549 SYSINIT(preempt_warning, SI_SUB_COPYRIGHT, SI_ORDER_ANY, printf_caddr_t,
550     preempt_warning)
551 #endif
552 #endif
553 
554 /************************************************************************
555  * SYSTEM RUN QUEUE manipulations and tests				*
556  ************************************************************************/
557 /*
558  * Initialize a run structure.
559  */
560 void
561 runq_init(struct runq *rq)
562 {
563 	int i;
564 
565 	bzero(rq, sizeof *rq);
566 	for (i = 0; i < RQ_NQS; i++)
567 		TAILQ_INIT(&rq->rq_queues[i]);
568 }
569 
570 /*
571  * Clear the status bit of the queue corresponding to priority level pri,
572  * indicating that it is empty.
573  */
574 static __inline void
575 runq_clrbit(struct runq *rq, int pri)
576 {
577 	struct rqbits *rqb;
578 
579 	rqb = &rq->rq_status;
580 	CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
581 	    rqb->rqb_bits[RQB_WORD(pri)],
582 	    rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
583 	    RQB_BIT(pri), RQB_WORD(pri));
584 	rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
585 }
586 
587 /*
588  * Find the index of the first non-empty run queue.  This is done by
589  * scanning the status bits, a set bit indicates a non-empty queue.
590  */
591 static __inline int
592 runq_findbit(struct runq *rq)
593 {
594 	struct rqbits *rqb;
595 	int pri;
596 	int i;
597 
598 	rqb = &rq->rq_status;
599 	for (i = 0; i < RQB_LEN; i++)
600 		if (rqb->rqb_bits[i]) {
601 			pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW);
602 			CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
603 			    rqb->rqb_bits[i], i, pri);
604 			return (pri);
605 		}
606 
607 	return (-1);
608 }
609 
610 /*
611  * Set the status bit of the queue corresponding to priority level pri,
612  * indicating that it is non-empty.
613  */
614 static __inline void
615 runq_setbit(struct runq *rq, int pri)
616 {
617 	struct rqbits *rqb;
618 
619 	rqb = &rq->rq_status;
620 	CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
621 	    rqb->rqb_bits[RQB_WORD(pri)],
622 	    rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
623 	    RQB_BIT(pri), RQB_WORD(pri));
624 	rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
625 }
626 
627 /*
628  * Add the KSE to the queue specified by its priority, and set the
629  * corresponding status bit.
630  */
631 void
632 runq_add(struct runq *rq, struct kse *ke)
633 {
634 	struct rqhead *rqh;
635 	int pri;
636 
637 	pri = ke->ke_thread->td_priority / RQ_PPQ;
638 	ke->ke_rqindex = pri;
639 	runq_setbit(rq, pri);
640 	rqh = &rq->rq_queues[pri];
641 	CTR5(KTR_RUNQ, "runq_add: td=%p ke=%p pri=%d %d rqh=%p",
642 	    ke->ke_thread, ke, ke->ke_thread->td_priority, pri, rqh);
643 	TAILQ_INSERT_TAIL(rqh, ke, ke_procq);
644 }
645 
646 /*
647  * Return true if there are runnable processes of any priority on the run
648  * queue, false otherwise.  Has no side effects, does not modify the run
649  * queue structure.
650  */
651 int
652 runq_check(struct runq *rq)
653 {
654 	struct rqbits *rqb;
655 	int i;
656 
657 	rqb = &rq->rq_status;
658 	for (i = 0; i < RQB_LEN; i++)
659 		if (rqb->rqb_bits[i]) {
660 			CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
661 			    rqb->rqb_bits[i], i);
662 			return (1);
663 		}
664 	CTR0(KTR_RUNQ, "runq_check: empty");
665 
666 	return (0);
667 }
668 
669 #if defined(SMP) && defined(SCHED_4BSD)
670 int runq_fuzz = 1;
671 SYSCTL_INT(_kern_sched, OID_AUTO, runq_fuzz, CTLFLAG_RW, &runq_fuzz, 0, "");
672 #endif
673 
674 /*
675  * Find the highest priority process on the run queue.
676  */
677 struct kse *
678 runq_choose(struct runq *rq)
679 {
680 	struct rqhead *rqh;
681 	struct kse *ke;
682 	int pri;
683 
684 	mtx_assert(&sched_lock, MA_OWNED);
685 	while ((pri = runq_findbit(rq)) != -1) {
686 		rqh = &rq->rq_queues[pri];
687 #if defined(SMP) && defined(SCHED_4BSD)
688 		/* fuzz == 1 is normal.. 0 or less are ignored */
689 		if (runq_fuzz > 1) {
690 			/*
691 			 * In the first couple of entries, check if
692 			 * there is one for our CPU as a preference.
693 			 */
694 			int count = runq_fuzz;
695 			int cpu = PCPU_GET(cpuid);
696 			struct kse *ke2;
697 			ke2 = ke = TAILQ_FIRST(rqh);
698 
699 			while (count-- && ke2) {
700 				if (ke->ke_thread->td_lastcpu == cpu) {
701 					ke = ke2;
702 					break;
703 				}
704 				ke2 = TAILQ_NEXT(ke2, ke_procq);
705 			}
706 		} else
707 #endif
708 			ke = TAILQ_FIRST(rqh);
709 		KASSERT(ke != NULL, ("runq_choose: no proc on busy queue"));
710 		CTR3(KTR_RUNQ,
711 		    "runq_choose: pri=%d kse=%p rqh=%p", pri, ke, rqh);
712 		return (ke);
713 	}
714 	CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
715 
716 	return (NULL);
717 }
718 
719 /*
720  * Remove the KSE from the queue specified by its priority, and clear the
721  * corresponding status bit if the queue becomes empty.
722  * Caller must set ke->ke_state afterwards.
723  */
724 void
725 runq_remove(struct runq *rq, struct kse *ke)
726 {
727 	struct rqhead *rqh;
728 	int pri;
729 
730 	KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
731 		("runq_remove: process swapped out"));
732 	pri = ke->ke_rqindex;
733 	rqh = &rq->rq_queues[pri];
734 	CTR5(KTR_RUNQ, "runq_remove: td=%p, ke=%p pri=%d %d rqh=%p",
735 	    ke->ke_thread, ke, ke->ke_thread->td_priority, pri, rqh);
736 	KASSERT(ke != NULL, ("runq_remove: no proc on busy queue"));
737 	TAILQ_REMOVE(rqh, ke, ke_procq);
738 	if (TAILQ_EMPTY(rqh)) {
739 		CTR0(KTR_RUNQ, "runq_remove: empty");
740 		runq_clrbit(rq, pri);
741 	}
742 }
743 
744 /****** functions that are temporarily here ***********/
745 #include <vm/uma.h>
746 #define RANGEOF(type, start, end) (offsetof(type, end) - offsetof(type, start))
747 extern struct mtx kse_zombie_lock;
748 
749 /*
750  *  Allocate scheduler specific per-process resources.
751  * The thread and ksegrp have already been linked in.
752  * In this case just set the default concurrency value.
753  *
754  * Called from:
755  *  proc_init() (UMA init method)
756  */
757 void
758 sched_newproc(struct proc *p, struct ksegrp *kg, struct thread *td)
759 {
760 
761 	/* This can go in sched_fork */
762 	sched_init_concurrency(kg);
763 }
764 
765 /*
766  * Called by the uma process fini routine..
767  * undo anything we may have done in the uma_init method.
768  * Panic if it's not all 1:1:1:1
769  * Called from:
770  *  proc_fini() (UMA method)
771  */
772 void
773 sched_destroyproc(struct proc *p)
774 {
775 
776 	/* this function slated for destruction */
777 	KASSERT((p->p_numthreads == 1), ("Cached proc with > 1 thread "));
778 	KASSERT((p->p_numksegrps == 1), ("Cached proc with > 1 ksegrp "));
779 }
780 
781 #define RANGEOF(type, start, end) (offsetof(type, end) - offsetof(type, start))
782 /*
783  * thread is being either created or recycled.
784  * Fix up the per-scheduler resources associated with it.
785  * Called from:
786  *  sched_fork_thread()
787  *  thread_dtor()  (*may go away)
788  *  thread_init()  (*may go away)
789  */
790 void
791 sched_newthread(struct thread *td)
792 {
793 	struct td_sched *ke;
794 
795 	ke = (struct td_sched *) (td + 1);
796 	bzero(ke, sizeof(*ke));
797 	td->td_sched     = ke;
798 	ke->ke_thread	= td;
799 	ke->ke_oncpu	= NOCPU;
800 	ke->ke_state	= KES_THREAD;
801 }
802 
803 /*
804  * Set up an initial concurrency of 1
805  * and set the given thread (if given) to be using that
806  * concurrency slot.
807  * May be used "offline"..before the ksegrp is attached to the world
808  * and thus wouldn't need schedlock in that case.
809  * Called from:
810  *  thr_create()
811  *  proc_init() (UMA) via sched_newproc()
812  */
813 void
814 sched_init_concurrency(struct ksegrp *kg)
815 {
816 
817 	kg->kg_concurrency = 1;
818 	kg->kg_avail_opennings = 1;
819 }
820 
821 /*
822  * Change the concurrency of an existing ksegrp to N
823  * Called from:
824  *  kse_create()
825  *  kse_exit()
826  *  thread_exit()
827  *  thread_single()
828  */
829 void
830 sched_set_concurrency(struct ksegrp *kg, int concurrency)
831 {
832 
833 	/* Handle the case for a declining concurrency */
834 	kg->kg_avail_opennings += (concurrency - kg->kg_concurrency);
835 	kg->kg_concurrency = concurrency;
836 }
837 
838 /*
839  * Called from thread_exit() for all exiting thread
840  *
841  * Not to be confused with sched_exit_thread()
842  * that is only called from thread_exit() for threads exiting
843  * without the rest of the process exiting because it is also called from
844  * sched_exit() and we wouldn't want to call it twice.
845  * XXX This can probably be fixed.
846  */
847 void
848 sched_thread_exit(struct thread *td)
849 {
850 
851 	td->td_ksegrp->kg_avail_opennings++;
852 	slot_fill(td->td_ksegrp);
853 }
854 
855 #endif /* KERN_SWITCH_INCLUDE */
856