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