![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sched_prim.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / osfmk / kern|
Return to sched_prim.c CVS log | Up to [Apple XNU] / XNU / osfmk / kern |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /*
23: * @OSF_FREE_COPYRIGHT@
24: */
25: /*
26: * Mach Operating System
27: * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
28: * All Rights Reserved.
29: *
30: * Permission to use, copy, modify and distribute this software and its
31: * documentation is hereby granted, provided that both the copyright
32: * notice and this permission notice appear in all copies of the
33: * software, derivative works or modified versions, and any portions
34: * thereof, and that both notices appear in supporting documentation.
35: *
36: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
37: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
38: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
39: *
40: * Carnegie Mellon requests users of this software to return to
41: *
42: * Software Distribution Coordinator or [email protected]
43: * School of Computer Science
44: * Carnegie Mellon University
45: * Pittsburgh PA 15213-3890
46: *
47: * any improvements or extensions that they make and grant Carnegie Mellon
48: * the rights to redistribute these changes.
49: */
50: /*
51: */
52: /*
53: * File: sched_prim.c
54: * Author: Avadis Tevanian, Jr.
55: * Date: 1986
56: *
57: * Scheduling primitives
58: *
59: */
60:
61: #include <debug.h>
62: #include <cpus.h>
63: #include <mach_kdb.h>
64: #include <simple_clock.h>
65: #include <mach_host.h>
66: #include <power_save.h>
67: #include <task_swapper.h>
68:
69: #include <ddb/db_output.h>
70: #include <mach/machine.h>
71: #include <machine/machine_routines.h>
72: #include <machine/sched_param.h>
73: #include <kern/ast.h>
74: #include <kern/clock.h>
75: #include <kern/counters.h>
76: #include <kern/cpu_number.h>
77: #include <kern/cpu_data.h>
78: #include <kern/etap_macros.h>
79: #include <kern/lock.h>
80: #include <kern/macro_help.h>
81: #include <kern/machine.h>
82: #include <kern/misc_protos.h>
83: #include <kern/processor.h>
84: #include <kern/queue.h>
85: #include <kern/sched.h>
86: #include <kern/sched_prim.h>
87: #include <kern/syscall_subr.h>
88: #include <kern/task.h>
89: #include <kern/thread.h>
90: #include <kern/thread_swap.h>
91: #include <vm/pmap.h>
92: #include <vm/vm_kern.h>
93: #include <vm/vm_map.h>
94: #include <mach/policy.h>
95: #include <mach/sync_policy.h>
96: #include <kern/sf.h>
97: #include <kern/mk_sp.h> /*** ??? fix so this can be removed ***/
98: #include <sys/kdebug.h>
99:
100: #if TASK_SWAPPER
101: #include <kern/task_swap.h>
102: extern int task_swap_on;
103: #endif /* TASK_SWAPPER */
104:
105: extern int hz;
106:
107: #define DEFAULT_PREEMPTION_RATE 100 /* (1/s) */
108: int default_preemption_rate = DEFAULT_PREEMPTION_RATE;
109: int min_quantum;
110:
111: unsigned sched_tick;
112:
113: #if SIMPLE_CLOCK
114: int sched_usec;
115: #endif /* SIMPLE_CLOCK */
116:
117: /* Forwards */
118: void thread_continue(thread_t);
119:
120: void wait_queues_init(void);
121:
122: void set_pri(
123: thread_t thread,
124: int pri,
125: int resched);
126:
127: thread_t choose_pset_thread(
128: processor_t myprocessor,
129: processor_set_t pset);
130:
131: thread_t choose_thread(
132: processor_t myprocessor);
133:
134: int run_queue_enqueue(
135: run_queue_t runq,
136: thread_t thread,
137: boolean_t tail);
138:
139: void idle_thread_continue(void);
140: void do_thread_scan(void);
141:
142: static
143: void clear_wait_internal(
144: thread_t thread,
145: int result);
146:
147:
148: void dump_run_queues(run_queue_t);
149: void dump_run_queue_struct( run_queue_t );
150: void dump_processor( processor_t );
151: void dump_processor_set( processor_set_t );
152:
153: #if DEBUG
154: void checkrq(
155: run_queue_t rq,
156: char *msg);
157:
158: void thread_check(
159: thread_t thread,
160: run_queue_t runq);
161: #endif /*DEBUG*/
162:
163: boolean_t thread_runnable(
164: thread_t thread);
165:
166: /*
167: * State machine
168: *
169: * states are combinations of:
170: * R running
171: * W waiting (or on wait queue)
172: * N non-interruptible
173: * O swapped out
174: * I being swapped in
175: *
176: * init action
177: * assert_wait thread_block clear_wait swapout swapin
178: *
179: * R RW, RWN R; setrun - -
180: * RN RWN RN; setrun - -
181: *
182: * RW W R -
183: * RWN WN RN -
184: *
185: * W R; setrun WO
186: * WN RN; setrun -
187: *
188: * RO - - R
189: *
190: */
191:
192: /*
193: * Waiting protocols and implementation:
194: *
195: * Each thread may be waiting for exactly one event; this event
196: * is set using assert_wait(). That thread may be awakened either
197: * by performing a thread_wakeup_prim() on its event,
198: * or by directly waking that thread up with clear_wait().
199: *
200: * The implementation of wait events uses a hash table. Each
201: * bucket is queue of threads having the same hash function
202: * value; the chain for the queue (linked list) is the run queue
203: * field. [It is not possible to be waiting and runnable at the
204: * same time.]
205: *
206: * Locks on both the thread and on the hash buckets govern the
207: * wait event field and the queue chain field. Because wakeup
208: * operations only have the event as an argument, the event hash
209: * bucket must be locked before any thread.
210: *
211: * Scheduling operations may also occur at interrupt level; therefore,
212: * interrupts below splsched() must be prevented when holding
213: * thread or hash bucket locks.
214: *
215: * The wait event hash table declarations are as follows:
216: */
217:
218: #define NUMQUEUES 59
219:
220: struct wait_queue wait_queues[NUMQUEUES];
221:
222: #define wait_hash(event) \
223: ((((int)(event) < 0)? ~(int)(event): (int)(event)) % NUMQUEUES)
224:
225: void
226: sched_init(void)
227: {
228: /*
229: * Calculate the minimum quantum
230: * in ticks.
231: */
232: if (default_preemption_rate < 1)
233: default_preemption_rate = DEFAULT_PREEMPTION_RATE;
234: min_quantum = hz / default_preemption_rate;
235: /*
236: * Round up result (4/5) to an
237: * integral number of ticks.
238: */
239: if (((hz * 10) / default_preemption_rate) - (min_quantum * 10) >= 5)
240: min_quantum++;
241: if (min_quantum < 1)
242: min_quantum = 1;
243: printf("minimum scheduling quantum is %d ms\n", (1000 / hz) * min_quantum);
244:
245: wait_queues_init();
246: pset_sys_bootstrap(); /* initialize processer mgmt. */
247: queue_init(&action_queue);
248: simple_lock_init(&action_lock, ETAP_THREAD_ACTION);
249: sched_tick = 0;
250: #if SIMPLE_CLOCK
251: sched_usec = 0;
252: #endif /* SIMPLE_CLOCK */
253: ast_init();
254: /*** ??? is this the right place?***/
255: sf_init();
256: }
257:
258: void
259: wait_queues_init(void)
260: {
261: register int i;
262:
263: for (i = 0; i < NUMQUEUES; i++) {
264: wait_queue_init(&wait_queues[i], SYNC_POLICY_FIFO);
265: }
266: }
267:
268: /*
269: * Thread timeout routine, called when timer expires.
270: */
271: void
272: thread_timer_expire(
273: thread_t thread)
274: {
275: spl_t s;
276:
277: s = splsched();
278: thread_lock(thread);
279: if ( thread->wait_timer_is_set &&
280: !thread_call_is_delayed(&thread->wait_timer, NULL) ) {
281: thread->wait_timer_is_set = FALSE;
282: if (thread->active)
283: clear_wait_internal(thread, THREAD_TIMED_OUT);
284: }
285: thread_unlock(thread);
286: splx(s);
287:
288: thread_deallocate(thread);
289: }
290:
291: /*
292: * thread_set_timer:
293: *
294: * Set a timer for the current thread, if the thread
295: * is ready to wait. Must be called between assert_wait()
296: * and thread_block().
297: */
298: void
299: thread_set_timer(
300: natural_t interval,
301: natural_t scale_factor)
302: {
303: thread_t thread = current_thread();
304: AbsoluteTime deadline;
305: spl_t s;
306:
307: s = splsched();
308: thread_lock(thread);
309: if ((thread->state & TH_WAIT) != 0) {
310: clock_interval_to_deadline(interval, scale_factor, &deadline);
311: thread_call_enter_delayed(&thread->wait_timer, deadline);
312: assert(!thread->wait_timer_is_set);
313: thread->ref_count++;
314: thread->wait_timer_is_set = TRUE;
315: }
316: thread_unlock(thread);
317: splx(s);
318: }
319:
320: void
321: thread_set_timer_deadline(
322: AbsoluteTime deadline)
323: {
324: thread_t thread = current_thread();
325: spl_t s;
326:
327: s = splsched();
328: thread_lock(thread);
329: if ((thread->state & TH_WAIT) != 0) {
330: thread_call_enter_delayed(&thread->wait_timer, deadline);
331: assert(!thread->wait_timer_is_set);
332: thread->ref_count++;
333: thread->wait_timer_is_set = TRUE;
334: }
335: thread_unlock(thread);
336: splx(s);
337: }
338:
339: void
340: thread_cancel_timer(void)
341: {
342: thread_t thread = current_thread();
343: boolean_t release = FALSE;
344: spl_t s;
345:
346: s = splsched();
347: thread_lock(thread);
348: if (thread->wait_timer_is_set) {
349: if (thread_call_cancel(&thread->wait_timer))
350: release = TRUE;
351: thread->wait_timer_is_set = FALSE;
352: }
353: thread_unlock(thread);
354: splx(s);
355:
356: if (release)
357: thread_deallocate(thread);
358: }
359:
360: /*
361: * thread_depress_timeout:
362: *
363: * Timeout routine for priority depression.
364: */
365: void
366: thread_depress_timeout(
367: thread_t thread)
368: {
369: sched_policy_t *policy;
370: spl_t s;
371:
372: s = splsched();
373: thread_lock(thread);
374: policy = policy_id_to_sched_policy(thread->policy);
375: thread_unlock(thread);
376: splx(s);
377:
378: if (policy != SCHED_POLICY_NULL)
379: policy->sp_ops.sp_thread_depress_timeout(policy, thread);
380:
381: thread_deallocate(thread);
382: }
383:
384: /*
385: * Set up thread timeout element when thread is created.
386: */
387: void
388: thread_timer_setup(
389: thread_t thread)
390: {
391: thread_call_setup(&thread->wait_timer, thread_timer_expire, thread);
392: thread->wait_timer_is_set = FALSE;
393: thread_call_setup(&thread->depress_timer, thread_depress_timeout, thread);
394: }
395:
396: /*
397: * Routine: thread_go_locked
398: * Purpose:
399: * Start a thread running.
400: * Conditions:
401: * thread lock held, IPC locks may be held.
402: * thread must have been pulled from wait queue under same lock hold.
403: */
404: void
405: thread_go_locked(
406: thread_t thread,
407: int result)
408: {
409: int state;
410: sched_policy_t *policy;
411: sf_return_t sfr;
412:
413: assert(thread->at_safe_point == FALSE);
414: assert(thread->wait_event == NO_EVENT);
415: assert(thread->wait_queue == WAIT_QUEUE_NULL);
416:
417: if (thread->state & TH_WAIT) {
418:
419: thread->state &= ~TH_WAIT;
420: if (!(thread->state & TH_RUN)) {
421: thread->state |= TH_RUN;
422: #if THREAD_SWAPPER
423: if (thread->state & TH_SWAPPED_OUT)
424: thread_swapin(thread->top_act, FALSE);
425: else
426: #endif /* THREAD_SWAPPER */
427: {
428: policy = &sched_policy[thread->policy];
429: sfr = policy->sp_ops.sp_thread_unblock(policy, thread);
430: assert(sfr == SF_SUCCESS);
431: }
432: }
433: thread->wait_result = result;
434: }
435:
436:
437: /*
438: * The next few lines are a major hack. Hopefully this will get us
439: * around all of the scheduling framework hooha. We can't call
440: * sp_thread_unblock yet because we could still be finishing up the
441: * durn two stage block on another processor and thread_setrun
442: * could be called by s_t_u and we'll really be messed up then.
443: */
444: /* Don't mess with this if we are still swapped out */
445: if (!(thread->state & TH_SWAPPED_OUT))
446: ((mk_sp_info_t)thread->sp_info)->th_state = MK_SP_RUNNABLE;
447:
448: }
449:
450: void
451: thread_mark_wait_locked(
452: thread_t thread,
453: int interruptible)
454: {
455:
456: assert(thread == current_thread());
457:
458: thread->wait_result = -1; /* JMM - Needed for non-assert kernel */
459: thread->state |= (interruptible) ? TH_WAIT : (TH_WAIT | TH_UNINT);
460: thread->at_safe_point = (interruptible == THREAD_ABORTSAFE);
461: thread->sleep_stamp = sched_tick;
462: }
463:
464:
465:
466: /*
467: * Routine: assert_wait_timeout
468: * Purpose:
469: * Assert that the thread intends to block,
470: * waiting for a timeout (no user known event).
471: */
472: unsigned int assert_wait_timeout_event;
473:
474: void
475: assert_wait_timeout(
476: mach_msg_timeout_t msecs,
477: int interruptible)
478: {
479: spl_t s;
480:
481: assert_wait((event_t)&assert_wait_timeout_event, interruptible);
482: thread_set_timer(msecs, 1000*NSEC_PER_USEC);
483: }
484:
485: /*
486: * Check to see if an assert wait is possible, without actually doing one.
487: * This is used by debug code in locks and elsewhere to verify that it is
488: * always OK to block when trying to take a blocking lock (since waiting
489: * for the actual assert_wait to catch the case may make it hard to detect
490: * this case.
491: */
492: boolean_t
493: assert_wait_possible(void)
494: {
495: thread_t thread = current_thread();
496:
497: return (thread == NULL || wait_queue_assert_possible(thread));
498: }
499:
500: /*
501: * assert_wait:
502: *
503: * Assert that the current thread is about to go to
504: * sleep until the specified event occurs.
505: */
506: void
507: assert_wait(
508: event_t event,
509: int interruptible)
510: {
511: register wait_queue_t wq;
512: register int index;
513:
514: assert(event != NO_EVENT);
515: assert(assert_wait_possible());
516:
517: index = wait_hash(event);
518: wq = &wait_queues[index];
519: wait_queue_assert_wait(wq,
520: event,
521: interruptible);
522: }
523:
524:
525: /*
526: * thread_[un]stop(thread)
527: * Once a thread has blocked interruptibly (via assert_wait) prevent
528: * it from running until thread_unstop.
529: *
530: * If someone else has already stopped the thread, wait for the
531: * stop to be cleared, and then stop it again.
532: *
533: * Return FALSE if interrupted.
534: *
535: * NOTE: thread_hold/thread_suspend should be called on the activation
536: * before calling thread_stop. TH_SUSP is only recognized when
537: * a thread blocks and only prevents clear_wait/thread_wakeup
538: * from restarting an interruptible wait. The wake_active flag is
539: * used to indicate that someone is waiting on the thread.
540: */
541: boolean_t
542: thread_stop(
543: thread_t thread)
544: {
545: spl_t s;
546:
547: s = splsched();
548: wake_lock(thread);
549:
550: while (thread->state & TH_SUSP) {
551: thread->wake_active = TRUE;
552: assert_wait((event_t)&thread->wake_active, THREAD_ABORTSAFE);
553: wake_unlock(thread);
554: splx(s);
555:
556: thread_block((void (*)(void)) 0);
557: if (current_thread()->wait_result != THREAD_AWAKENED)
558: return (FALSE);
559:
560: s = splsched();
561: wake_lock(thread);
562: }
563: thread_lock(thread);
564: thread->state |= TH_SUSP;
565: thread_unlock(thread);
566:
567: wake_unlock(thread);
568: splx(s);
569:
570: return (TRUE);
571: }
572:
573: /*
574: * Clear TH_SUSP and if the thread has been stopped and is now runnable,
575: * put it back on the run queue.
576: */
577: void
578: thread_unstop(
579: thread_t thread)
580: {
581: sched_policy_t *policy;
582: sf_return_t sfr;
583: spl_t s;
584:
585: s = splsched();
586: wake_lock(thread);
587: thread_lock(thread);
588:
589: if ((thread->state & (TH_RUN|TH_WAIT|TH_SUSP/*|TH_UNINT*/)) == TH_SUSP) {
590: thread->state = (thread->state & ~TH_SUSP) | TH_RUN;
591: #if THREAD_SWAPPER
592: if (thread->state & TH_SWAPPED_OUT)
593: thread_swapin(thread->top_act, FALSE);
594: else
595: #endif /* THREAD_SWAPPER */
596: {
597: policy = &sched_policy[thread->policy];
598: sfr = policy->sp_ops.sp_thread_unblock(policy, thread);
599: assert(sfr == SF_SUCCESS);
600: }
601: }
602: else
603: if (thread->state & TH_SUSP) {
604: thread->state &= ~TH_SUSP;
605:
606: if (thread->wake_active) {
607: thread->wake_active = FALSE;
608: thread_unlock(thread);
609: wake_unlock(thread);
610: splx(s);
611: thread_wakeup((event_t)&thread->wake_active);
612:
613: return;
614: }
615: }
616:
617: thread_unlock(thread);
618: wake_unlock(thread);
619: splx(s);
620: }
621:
622: /*
623: * Wait for the thread's RUN bit to clear
624: */
625: boolean_t
626: thread_wait(
627: thread_t thread)
628: {
629: spl_t s;
630:
631: s = splsched();
632: wake_lock(thread);
633:
634: while (thread->state & (TH_RUN/*|TH_UNINT*/)) {
635: if (thread->last_processor != PROCESSOR_NULL)
636: cause_ast_check(thread->last_processor);
637:
638: thread->wake_active = TRUE;
639: assert_wait((event_t)&thread->wake_active, THREAD_ABORTSAFE);
640: wake_unlock(thread);
641: splx(s);
642:
643: thread_block((void (*)(void))0);
644: if (current_thread()->wait_result != THREAD_AWAKENED)
645: return (FALSE);
646:
647: s = splsched();
648: wake_lock(thread);
649: }
650:
651: wake_unlock(thread);
652: splx(s);
653:
654: return (TRUE);
655: }
656:
657:
658: /*
659: * thread_stop_wait(thread)
660: * Stop the thread then wait for it to block interruptibly
661: */
662: boolean_t
663: thread_stop_wait(
664: thread_t thread)
665: {
666: if (thread_stop(thread)) {
667: if (thread_wait(thread))
668: return (TRUE);
669:
670: thread_unstop(thread);
671: }
672:
673: return (FALSE);
674: }
675:
676:
677: static
678: void
679: clear_wait_internal(
680: thread_t thread,
681: int result)
682: {
683: register int index;
684: register queue_t q;
685: register event_t event;
686: register simple_lock_t lock;
687: sched_policy_t *policy;
688: sf_return_t sfr;
689:
690: /*
691: * If the thread isn't in a wait queue, just set it running. Otherwise,
692: * try to remove it from the queue and, if successful, then set it
693: * running.
694: */
695: if (wait_queue_assert_possible(thread) ||
696: (wait_queue_remove(thread) == KERN_SUCCESS)) {
697: thread_go_locked(thread, result);
698: }
699: }
700:
701: /*
702: * clear_wait:
703: *
704: * Clear the wait condition for the specified thread. Start the thread
705: * executing if that is appropriate.
706: *
707: * parameters:
708: * thread thread to awaken
709: * result Wakeup result the thread should see
710: * interruptible Don't wake up the thread if it isn't interruptible.
711: */
712: void
713: clear_wait(
714: thread_t thread,
715: int result,
716: boolean_t interruptible)
717: {
718: spl_t s;
719:
720: s = splsched();
721: thread_lock(thread);
722: if (!interruptible || !(thread->state & TH_UNINT))
723: clear_wait_internal(thread, result);
724: thread_unlock(thread);
725: splx(s);
726: }
727:
728:
729: /*
730: * thread_wakeup_prim:
731: *
732: * Common routine for thread_wakeup, thread_wakeup_with_result,
733: * and thread_wakeup_one.
734: *
735: */
736: void
737: thread_wakeup_prim(
738: event_t event,
739: boolean_t one_thread,
740: int result)
741: {
742: register wait_queue_t wq;
743: register int index;
744:
745: index = wait_hash(event);
746: wq = &wait_queues[index];
747: if (one_thread)
748: wait_queue_wakeup_one(wq, event, result);
749: else
750: wait_queue_wakeup_all(wq, event, result);
751: }
752:
753: /*
754: * thread_bind:
755: *
756: * Force a thread to execute on the specified processor.
757: * If the thread is currently executing, it may wait until its
758: * time slice is up before switching onto the specified processor.
759: *
760: * A processor of PROCESSOR_NULL causes the thread to be unbound.
761: * xxx - DO NOT export this to users.
762: */
763: void
764: thread_bind(
765: register thread_t thread,
766: processor_t processor)
767: {
768: spl_t s;
769:
770: s = splsched();
771: thread_lock(thread);
772: thread_bind_locked(thread, processor);
773: thread_unlock(thread);
774: splx(s);
775: }
776:
777: /*
778: * Select a thread for this processor (the current processor) to run.
779: * May select the current thread.
780: * Assumes splsched.
781: */
782: thread_t
783: thread_select(
784: register processor_t myprocessor)
785: {
786: register thread_t thread;
787: processor_set_t pset;
788: register run_queue_t runq = &myprocessor->runq;
789: boolean_t other_runnable;
790: sched_policy_t *policy;
791: sf_return_t sfr;
792:
793: /*
794: * Check for other non-idle runnable threads.
795: */
796: myprocessor->first_quantum = TRUE;
797: pset = myprocessor->processor_set;
798: thread = current_thread();
799:
800: #if 0 /* CHECKME! */
801: thread->unconsumed_quantum = myprocessor->quantum;
802: #endif
803:
804: simple_lock(&runq->lock);
805: simple_lock(&pset->runq.lock);
806:
807: other_runnable = runq->count > 0 || pset->runq.count > 0;
808:
809: if ( (!other_runnable ||
810: (runq->highq < thread->sched_pri &&
811: pset->runq.highq < thread->sched_pri)) &&
812: #if MACH_HOST
813: thread->processor_set == pset &&
814: #endif /* MACH_HOST */
815: (thread->bound_processor == PROCESSOR_NULL ||
816: thread->bound_processor == myprocessor) &&
817: thread->state == TH_RUN &&
818: thread->pending_policy == POLICY_NULL ) {
819:
820: /* I am the highest priority runnable thread: */
821: simple_unlock(&pset->runq.lock);
822: simple_unlock(&runq->lock);
823:
824: /* Update the thread's meta-priority */
825: policy = &sched_policy[thread->policy];
826: /*** ??? maybe use a macro ***/
827: sfr = policy->sp_ops.sp_thread_update_mpri(policy, thread);
828: assert(sfr == SF_SUCCESS);
829: }
830: else if (other_runnable) {
831: simple_unlock(&pset->runq.lock);
832: simple_unlock(&runq->lock);
833: thread = choose_thread(myprocessor);
834: }
835: else {
836: simple_unlock(&runq->lock);
837:
838: /*
839: * Nothing non-idle runnable, including myself.
840: * Return if this
841: * thread is still runnable on this processor.
842: * Check for priority update if required.
843: */
844: /* get an idle thread to run */
845: thread = choose_pset_thread(myprocessor, pset);
846: }
847:
848: if (thread->policy & (POLICY_RR|POLICY_FIFO))
849: #if 1 /* CHECKME! */
850: myprocessor->quantum = pset->set_quantum;
851: #else
852: myprocessor->quantum = thread->unconsumed_quantum;
853: #endif
854: else
855: myprocessor->quantum = thread->bound_processor?
856: min_quantum : pset->set_quantum;
857:
858: return (thread);
859: }
860:
861:
862: /*
863: * Stop running the current thread and start running the new thread.
864: * If continuation is non-zero, and the current thread is blocked,
865: * then it will resume by executing continuation on a new stack.
866: * Returns TRUE if the hand-off succeeds.
867: * The reason parameter == AST_QUANTUM if the thread blocked
868: * because its quantum expired.
869: * Assumes splsched.
870: */
871:
872:
873: static thread_t
874: __current_thread(void)
875: {
876: return (current_thread());
877: }
878:
879:
880: boolean_t
881: thread_invoke(
882: register thread_t old_thread,
883: register thread_t new_thread,
884: int reason,
885: void (*continuation)(void))
886: {
887: sched_policy_t *policy;
888: sf_return_t sfr;
889: thread_t old_thread_hold;
890: void (*lcont)(void);
891:
892: /*
893: * Mark thread interruptible.
894: */
895: thread_lock(new_thread);
896: new_thread->state &= ~TH_UNINT;
897:
898: assert(thread_runnable(new_thread));
899:
900: /*
901: * Check for invoking the same thread.
902: */
903: if (old_thread == new_thread) {
904: counter(++c_thread_invoke_same);
905: thread_unlock(new_thread);
906: if (continuation != (void (*)()) 0) {
907: if (old_thread->funnel_state & TH_FN_REFUNNEL) {
908: kern_return_t save_wait_result;
909: old_thread->funnel_state = 0;
910: save_wait_result = old_thread->wait_result;
911: mutex_lock(&funnel_lock);
912: old_thread->funnel_state = TH_FN_OWNED;
913: old_thread->wait_result = save_wait_result;
914: }
915: (void) spllo();
916: call_continuation(continuation);
917: /*NOTREACHED*/
918: }
919: return TRUE;
920: }
921:
922: if ((old_thread->stack_privilege != current_stack()) &&
923: (continuation != (void (*)()) 0))
924: {
925: switch (new_thread->state & TH_STACK_STATE) {
926: case TH_STACK_HANDOFF:
927: new_thread->state &= ~(TH_STACK_HANDOFF|TH_UNINT);
928: thread_unlock(new_thread);
929:
930: mp_disable_preemption();
931: new_thread->last_processor = current_processor();
932: mp_enable_preemption();
933:
934: /*
935: * Set up ast context of new thread and switch to its timer.
936: */
937: mp_disable_preemption();
938: ast_context(new_thread->top_act, cpu_number());
939: mp_enable_preemption();
940: timer_switch(&new_thread->system_timer);
941:
942: old_thread->continuation = continuation;
943: stack_handoff(old_thread, new_thread);
944: act_machine_sv_free(old_thread->top_act);
945:
946: thread_lock(old_thread);
947:
948: /*
949: * inline thread_dispatch but don't free stack
950: */
951:
952: switch (old_thread->state & (TH_RUN|TH_WAIT|TH_UNINT|TH_IDLE)) {
953: sched_policy_t *policy;
954: sf_return_t sfr;
955:
956: case TH_RUN | TH_UNINT:
957: case TH_RUN:
958: /*
959: * No reason to stop. Put back on a run queue.
960: */
961: old_thread->state |= TH_STACK_HANDOFF;
962:
963: /* Get pointer to scheduling policy "object" */
964: policy = &sched_policy[old_thread->policy];
965:
966: /* Leave enqueueing thread up to scheduling policy */
967: sfr = policy->sp_ops.sp_thread_dispatch(policy,
968: old_thread);
969: assert(sfr == SF_SUCCESS);
970:
971: break;
972:
973: case TH_RUN | TH_WAIT | TH_UNINT:
974: case TH_RUN | TH_WAIT:
975: old_thread->sleep_stamp = sched_tick;
976:
977: /* fallthrough */
978: case TH_WAIT: /* this happens! */
979:
980: /*
981: * Waiting
982: */
983: old_thread->state |= TH_STACK_HANDOFF;
984: old_thread->state &= ~TH_RUN;
985: if (old_thread->state & TH_TERMINATE)
986: thread_reaper_enqueue(old_thread);
987:
988: if (old_thread->wake_active) {
989: old_thread->wake_active = FALSE;
990: thread_unlock(old_thread);
991: thread_wakeup((event_t)&old_thread->wake_active);
992: goto after_old_thread;
993: }
994: break;
995:
996: case TH_RUN | TH_IDLE:
997: /*
998: * Drop idle thread -- it is already in
999: * idle_thread_array.
1000: */
1001: old_thread->state |= TH_STACK_HANDOFF;
1002:
1003: break;
1004:
1005: default:
1006: panic("State 0x%x \n",old_thread->state);
1007: }
1008:
1009: thread_unlock(old_thread);
1010: after_old_thread:
1011: /*
1012: * call_continuation calls the continuation after
1013: resetting the current stack pointer to recover
1014: stack space. without this we could stack overflow
1015: */
1016: disable_preemption();
1017:
1018: thread_lock(old_thread);
1019:
1020: /* Get pointer to scheduling policy "object" */
1021: policy = &sched_policy[old_thread->policy];
1022:
1023: /* Indicate to sched policy that old thread has stopped execution */
1024: /*** ??? maybe use a macro -- rkc, 1/4/96 ***/
1025: sfr = policy->sp_ops.sp_thread_done(policy,
1026: old_thread);
1027: assert(sfr == SF_SUCCESS);
1028:
1029: /* Process any pending scheduling policy change */
1030: if (old_thread->pending_policy != POLICY_NULL) {
1031: sched_policy_t *policy;
1032: sf_return_t sfr;
1033: if (old_thread->policy != old_thread->pending_policy) {
1034: /* Detach thread from current scheduling policy */
1035: sfr = policy->sp_ops.sp_thread_detach(
1036: policy,
1037: old_thread);
1038: assert(sfr == SF_SUCCESS);
1039:
1040: /* Attach to the pending policy */
1041: policy = &sched_policy[old_thread->pending_policy];
1042: sfr = policy->sp_ops.sp_thread_attach(
1043: policy,
1044: old_thread);
1045:
1046: /* Save result for issuer of policy change */
1047: old_thread->change_sfr = (kern_return_t)sfr;
1048:
1049: /* If successful so far, set up sched attributes */
1050: if (sfr == SF_SUCCESS) {
1051: sfr = policy->sp_ops.sp_thread_set(
1052: policy,
1053: old_thread,
1054: old_thread->pending_sched_attr);
1055:
1056: /* Save result for issuer of policy change */
1057: old_thread->change_sfr = (kern_return_t)sfr;
1058: }
1059: }
1060:
1061: /* Indicate change has been done */
1062: old_thread->pending_policy = POLICY_NULL;
1063: }
1064: thread_unlock(old_thread);
1065: thread_lock(new_thread);
1066:
1067: assert(thread_runnable(new_thread));
1068:
1069: /* Get pointer to scheduling policy "object" */
1070: policy = &sched_policy[new_thread->policy];
1071:
1072: /* Indicate to sched policy that new thread has started execution */
1073: /*** ??? maybe use a macro ***/
1074: sfr = policy->sp_ops.sp_thread_begin(policy, new_thread);
1075: assert(sfr == SF_SUCCESS);
1076: thread_unlock(new_thread);
1077: enable_preemption();
1078:
1079: counter_always(c_thread_invoke_hits++);
1080: (void) spllo();
1081: lcont = new_thread->continuation;
1082: assert(lcont);
1083: if (new_thread->funnel_state & TH_FN_REFUNNEL) {
1084: kern_return_t save_wait_result;
1085: new_thread->funnel_state = 0;
1086: save_wait_result = new_thread->wait_result;
1087: mutex_lock(&funnel_lock);
1088: new_thread->funnel_state = TH_FN_OWNED;
1089: new_thread->wait_result = save_wait_result;
1090: }
1091: assert(lcont);
1092: call_continuation(lcont);
1093: /*NOTREACHED*/
1094: return TRUE;
1095:
1096: case TH_STACK_COMING_IN:
1097: /*
1098: * waiting for a stack
1099: */
1100: thread_swapin(new_thread);
1101: thread_unlock(new_thread);
1102: counter_always(c_thread_invoke_misses++);
1103: return FALSE;
1104:
1105: case 0:
1106: /*
1107: * already has a stack - can't handoff
1108: */
1109:
1110: break;
1111: }
1112: }
1113: else
1114: {
1115: /*
1116: * check that the new thread has a stack
1117: */
1118: if (new_thread->state & TH_STACK_HANDOFF) {
1119: /* has no stack. if not already waiting for one try to get one */
1120: if ((new_thread->state & TH_STACK_COMING_IN) ||
1121: /* not already waiting. nonblocking try to get one */
1122: !stack_alloc_try(new_thread, thread_continue))
1123: {
1124: /* couldn't get one. schedule new thread to get a stack and
1125: return failure so we can try another thread. */
1126: thread_swapin(new_thread);
1127: thread_unlock(new_thread);
1128: counter_always(c_thread_invoke_misses++);
1129: return FALSE;
1130: }
1131: }
1132: /* new thread now has a stack. it has been setup to resume in
1133: thread_continue so it can dispatch the old thread, deal with
1134: funnelling and then go to it's true continuation point */
1135: }
1136:
1137: new_thread->state &= ~(TH_STACK_HANDOFF | TH_UNINT);
1138:
1139: /*
1140: * Thread is now interruptible.
1141: */
1142: mp_disable_preemption();
1143: new_thread->last_processor = current_processor();
1144: mp_enable_preemption();
1145:
1146: thread_unlock(new_thread);
1147:
1148: /*
1149: * Set up ast context of new thread and switch to its timer.
1150: */
1151: mp_disable_preemption();
1152: ast_context(new_thread->top_act, cpu_number());
1153: mp_enable_preemption();
1154: timer_switch(&new_thread->system_timer);
1155:
1156: /*
1157: * switch_context is machine-dependent. It does the
1158: * machine-dependent components of a context-switch, like
1159: * changing address spaces. It updates active_threads.
1160: */
1161: old_thread->reason = reason;
1162: counter_always(c_thread_invoke_csw++);
1163: current_task()->csw++;
1164:
1165: /*
1166: * N.B. On return from the call to switch_context, 'old_thread'
1167: * points at the thread that yielded to us. Unfortunately, at
1168: * this point, there are no simple_locks held, so if we are preempted
1169: * before the call to thread_dispatch blocks preemption, it is
1170: * possible for 'old_thread' to terminate, leaving us with a
1171: * stale thread pointer.
1172: */
1173: assert(thread_runnable(new_thread));
1174: assert(old_thread->runq == RUN_QUEUE_NULL);
1175:
1176: disable_preemption();
1177:
1178: thread_lock(old_thread);
1179:
1180: /* Indicate to sched policy that old thread has stopped execution */
1181: policy = &sched_policy[old_thread->policy];
1182: /*** ??? maybe use a macro -- ***/
1183: sfr = policy->sp_ops.sp_thread_done(policy, old_thread);
1184: assert(sfr == SF_SUCCESS);
1185:
1186: /* Process any pending scheduling policy change */
1187: if (old_thread->pending_policy != POLICY_NULL) {
1188: if (old_thread->policy != old_thread->pending_policy) {
1189: /* Detach thread from current scheduling policy */
1190: sfr = policy->sp_ops.sp_thread_detach(policy, old_thread);
1191: assert(sfr == SF_SUCCESS);
1192:
1193: /* Attach to the pending policy */
1194: policy = &sched_policy[old_thread->pending_policy];
1195: sfr = policy->sp_ops.sp_thread_attach(policy, old_thread);
1196:
1197: /* Save result for issuer of policy change */
1198: old_thread->change_sfr = (kern_return_t)sfr;
1199:
1200: /* If successful so far, set up sched attributes */
1201: if (sfr == SF_SUCCESS) {
1202: sfr = policy->sp_ops.sp_thread_set(policy, old_thread,
1203: old_thread->pending_sched_attr);
1204:
1205: /* Save result for issuer of policy change */
1206: old_thread->change_sfr = (kern_return_t)sfr;
1207: }
1208: }
1209:
1210: /* Indicate change has been done */
1211: old_thread->pending_policy = POLICY_NULL;
1212: }
1213:
1214: thread_unlock(old_thread);
1215: old_thread_hold = old_thread;
1216:
1217: /* SWITCH CONTEXT HERE */
1218:
1219: old_thread = switch_context(old_thread, continuation, new_thread);
1220:
1221: /* Now on new thread's stack. Set a local variable to refer to it. */
1222: new_thread = __current_thread();
1223: assert(old_thread != new_thread);
1224:
1225: assert(thread_runnable(new_thread));
1226:
1227: thread_lock(new_thread);
1228: assert(thread_runnable(new_thread));
1229: /* Indicate to sched policy that new thread has started execution */
1230: policy = &sched_policy[new_thread->policy];
1231: /*** ??? maybe use a macro -- rkc, 1/4/96 ***/
1232: sfr = policy->sp_ops.sp_thread_begin(policy, new_thread);
1233: assert(sfr == SF_SUCCESS);
1234: thread_unlock(new_thread);
1235:
1236: /*
1237: * We're back. Now old_thread is the thread that resumed
1238: * us, and we have to dispatch it.
1239: */
1240: /* CHECKME! */
1241: // Code from OSF in Grenoble deleted the following fields. They were
1242: // used in HPPA and 386 code, but not in the PPC for other than
1243: // just setting and resetting. They didn't delete these lines from
1244: // the MACH_RT builds, though, causing compile errors. I'm going
1245: // to make a wild guess and assume we can just delete these.
1246: #if 0
1247: if (old_thread->preempt == TH_NOT_PREEMPTABLE) {
1248: /*
1249: * Mark that we have been really preempted
1250: */
1251: old_thread->preempt = TH_PREEMPTED;
1252: }
1253: #endif
1254: thread_dispatch(old_thread);
1255: enable_preemption();
1256: return TRUE;
1257: }
1258:
1259: /*
1260: * thread_continue:
1261: *
1262: * Called when the launching a new thread, at splsched();
1263: */
1264: void
1265: thread_continue(
1266: register thread_t old_thread)
1267: {
1268: register thread_t self;
1269: register void (*continuation)();
1270: sched_policy_t *policy;
1271: sf_return_t sfr;
1272:
1273: self = current_thread();
1274: continuation = self->continuation;
1275:
1276: /*
1277: * We must dispatch the old thread and then
1278: * call the current thread's continuation.
1279: * There might not be an old thread, if we are
1280: * the first thread to run on this processor.
1281: */
1282: if (old_thread != THREAD_NULL) {
1283: thread_dispatch(old_thread);
1284: thread_lock(self);
1285:
1286: /* Get pointer to scheduling policy "object" */
1287: policy = &sched_policy[self->policy];
1288:
1289: /* Indicate to sched policy that new thread has started execution */
1290: /*** ??? maybe use a macro -- rkc, 1/4/96 ***/
1291: sfr = policy->sp_ops.sp_thread_begin(policy,self);
1292: assert(sfr == SF_SUCCESS);
1293: thread_unlock(self);
1294: }
1295:
1296: /*
1297: * N.B. - the following is necessary, since thread_invoke()
1298: * inhibits preemption on entry and reenables before it
1299: * returns. Unfortunately, the first time a newly-created
1300: * thread executes, it magically appears here, and never
1301: * executes the enable_preemption() call in thread_invoke().
1302: */
1303: enable_preemption();
1304: if (self->funnel_state & TH_FN_REFUNNEL) {
1305: kern_return_t save_wait_result;
1306: self->funnel_state = 0;
1307: save_wait_result = self->wait_result;
1308: mutex_lock(&funnel_lock);
1309: self->wait_result = save_wait_result;
1310: self->funnel_state = TH_FN_OWNED;
1311: }
1312: spllo();
1313:
1314: assert(continuation);
1315: (*continuation)();
1316: /*NOTREACHED*/
1317: }
1318:
1319: #if MACH_LDEBUG || MACH_KDB
1320:
1321: #define THREAD_LOG_SIZE 300
1322:
1323: struct t64 {
1324: unsigned long h;
1325: unsigned long l;
1326: };
1327:
1328: struct {
1329: struct t64 stamp;
1330: thread_t thread;
1331: long info1;
1332: long info2;
1333: long info3;
1334: char * action;
1335: } thread_log[THREAD_LOG_SIZE];
1336:
1337: int thread_log_index;
1338:
1339: void check_thread_time(long n);
1340:
1341:
1342: int check_thread_time_crash;
1343:
1344: #if 0
1345: void
1346: check_thread_time(long us)
1347: {
1348: struct t64 temp;
1349:
1350: if (!check_thread_time_crash)
1351: return;
1352:
1353: temp = thread_log[0].stamp;
1354: cyctm05_diff (&thread_log[1].stamp, &thread_log[0].stamp, &temp);
1355:
1356: if (temp.l >= us && thread_log[1].info != 0x49) /* HACK!!! */
1357: panic ("check_thread_time");
1358: }
1359: #endif
1360:
1361: void
1362: log_thread_action(char * action, long info1, long info2, long info3)
1363: {
1364: int i;
1365: spl_t x;
1366: static unsigned int tstamp;
1367:
1368: x = splhigh();
1369:
1370: for (i = THREAD_LOG_SIZE-1; i > 0; i--) {
1371: thread_log[i] = thread_log[i-1];
1372: }
1373:
1374: thread_log[0].stamp.h = 0;
1375: thread_log[0].stamp.l = tstamp++;
1376: thread_log[0].thread = current_thread();
1377: thread_log[0].info1 = info1;
1378: thread_log[0].info2 = info2;
1379: thread_log[0].info3 = info3;
1380: thread_log[0].action = action;
1381: /* strcpy (&thread_log[0].action[0], action);*/
1382:
1383: splx(x);
1384: }
1385: #endif /* MACH_LDEBUG || MACH_KDB */
1386:
1387: #if MACH_KDB
1388: #include <ddb/db_output.h>
1389: void db_show_thread_log(void);
1390:
1391: void
1392: db_show_thread_log(void)
1393: {
1394: int i;
1395:
1396: db_printf ("%s %s %s %s %s %s\n", " Thread ", " Info1 ", " Info2 ",
1397: " Info3 ", " Timestamp ", "Action");
1398:
1399: for (i = 0; i < THREAD_LOG_SIZE; i++) {
1400: db_printf ("%08x %08x %08x %08x %08x/%08x %s\n",
1401: thread_log[i].thread,
1402: thread_log[i].info1,
1403: thread_log[i].info2,
1404: thread_log[i].info3,
1405: thread_log[i].stamp.h,
1406: thread_log[i].stamp.l,
1407: thread_log[i].action);
1408: }
1409: }
1410: #endif /* MACH_KDB */
1411:
1412: /*
1413: * thread_block_reason:
1414: *
1415: * Block the current thread. If the thread is runnable
1416: * then someone must have woken it up between its request
1417: * to sleep and now. In this case, it goes back on a
1418: * run queue.
1419: *
1420: * If a continuation is specified, then thread_block will
1421: * attempt to discard the thread's kernel stack. When the
1422: * thread resumes, it will execute the continuation function
1423: * on a new kernel stack.
1424: */
1425: counter(mach_counter_t c_thread_block_calls = 0;)
1426:
1427: int
1428: thread_block_reason(
1429: void (*continuation)(void),
1430: int reason)
1431: {
1432: register thread_t thread = current_thread();
1433: register processor_t myprocessor;
1434: register thread_t new_thread;
1435: register int aborted;
1436: spl_t s;
1437:
1438: counter(++c_thread_block_calls);
1439:
1440: check_simple_locks();
1441:
1442: if (thread->funnel_state & TH_FN_OWNED) {
1443: thread->funnel_state = TH_FN_REFUNNEL;
1444: mutex_unlock(&funnel_lock);
1445: }
1446:
1447: machine_clock_assist();
1448:
1449: s = splsched();
1450: mp_disable_preemption();
1451: myprocessor = current_processor();
1452:
1453: thread_lock(thread);
1454: aborted = (thread->state & TH_ABORT);
1455: if (aborted)
1456: clear_wait_internal(thread, THREAD_INTERRUPTED);
1457:
1458: /* Unconditionally remove either | both */
1459: ast_off(AST_QUANTUM|AST_BLOCK|AST_URGENT);
1460:
1461: mp_enable_preemption();
1462:
1463: new_thread = thread_select(myprocessor);
1464: assert(new_thread);
1465: assert(thread_runnable(new_thread));
1466: thread_unlock(thread);
1467: while (!thread_invoke(thread, new_thread, reason, continuation)) {
1468: thread_lock(thread);
1469: new_thread = thread_select(myprocessor);
1470: assert(new_thread);
1471: assert(thread_runnable(new_thread));
1472: thread_unlock(thread);
1473: }
1474:
1475: splx(s);
1476:
1477: if (thread->funnel_state & TH_FN_REFUNNEL) {
1478: kern_return_t save_wait_result;
1479:
1480: save_wait_result = thread->wait_result;
1481: thread->funnel_state = 0;
1482: mutex_lock(&funnel_lock);
1483: thread->funnel_state = TH_FN_OWNED;
1484: thread->wait_result = save_wait_result;
1485: }
1486:
1487: return thread->wait_result;
1488: }
1489:
1490: /*
1491: * thread_block:
1492: *
1493: * Now calls thread_block_reason() which forwards the
1494: * the reason parameter to thread_invoke() so it can
1495: * do the right thing if the thread's quantum expired.
1496: */
1497: int
1498: thread_block(
1499: void (*continuation)(void))
1500: {
1501: return thread_block_reason(continuation, 0);
1502: }
1503:
1504: /*
1505: * thread_run:
1506: *
1507: * Switch directly from the current thread to a specified
1508: * thread. Both the current and new threads must be
1509: * runnable.
1510: */
1511: void
1512: thread_run(
1513: void (*continuation)(void),
1514: register thread_t new_thread)
1515: {
1516: register thread_t thread = current_thread();
1517: spl_t s;
1518:
1519: s = splsched();
1520: while (!thread_invoke(thread, new_thread, 0, continuation)) {
1521: register processor_t myprocessor = current_processor();
1522: thread_lock(thread);
1523: new_thread = thread_select(myprocessor);
1524: thread_unlock(thread);
1525: }
1526: splx(s);
1527: }
1528:
1529: /*
1530: * Dispatches a running thread that is not on a runq.
1531: * Called at splsched.
1532: */
1533: void
1534: thread_dispatch(
1535: register thread_t thread)
1536: {
1537: sched_policy_t *policy;
1538: sf_return_t sfr;
1539:
1540: /*
1541: * If we are discarding the thread's stack, we must do it
1542: * before the thread has a chance to run.
1543: */
1544: wake_lock(thread);
1545: thread_lock(thread);
1546:
1547: if (thread->continuation != (void (*)())0) {
1548: assert((thread->state & TH_STACK_STATE) == 0);
1549: thread->state |= TH_STACK_HANDOFF;
1550:
1551: stack_free(thread);
1552: if (thread->top_act) {
1553: act_machine_sv_free(thread->top_act);
1554: }
1555: }
1556:
1557: switch (thread->state & (TH_RUN|TH_WAIT|TH_UNINT|TH_IDLE)) {
1558:
1559: case TH_RUN | TH_UNINT:
1560: case TH_RUN:
1561: /*
1562: * No reason to stop. Put back on a run queue.
1563: */
1564: /* Leave enqueueing thread up to scheduling policy */
1565: policy = &sched_policy[thread->policy];
1566: /*** ??? maybe use a macro ***/
1567: sfr = policy->sp_ops.sp_thread_dispatch(policy, thread);
1568: assert(sfr == SF_SUCCESS);
1569: break;
1570:
1571: case TH_RUN | TH_WAIT | TH_UNINT:
1572: case TH_RUN | TH_WAIT:
1573: thread->sleep_stamp = sched_tick;
1574: /* fallthrough */
1575: case TH_WAIT: /* this happens! */
1576:
1577: /*
1578: * Waiting
1579: */
1580: thread->state &= ~TH_RUN;
1581: if (thread->state & TH_TERMINATE)
1582: thread_reaper_enqueue(thread);
1583:
1584: if (thread->wake_active) {
1585: thread->wake_active = FALSE;
1586: thread_unlock(thread);
1587: wake_unlock(thread);
1588: thread_wakeup((event_t)&thread->wake_active);
1589: return;
1590: }
1591: break;
1592:
1593: case TH_RUN | TH_IDLE:
1594: /*
1595: * Drop idle thread -- it is already in
1596: * idle_thread_array.
1597: */
1598: break;
1599:
1600: default:
1601: panic("State 0x%x \n",thread->state);
1602: }
1603: thread_unlock(thread);
1604: wake_unlock(thread);
1605: }
1606:
1607: /*
1608: * Enqueue thread on run_queue.
1609: */
1610: int
1611: run_queue_enqueue(
1612: register run_queue_t rq,
1613: register thread_t thread,
1614: boolean_t tail)
1615: {
1616: register int whichq;
1617: int oldrqcount;
1618:
1619: whichq = thread->sched_pri;
1620: if (whichq > MAXPRI || whichq < MINPRI) {
1621: panic("run_queue_enqueue: bad pri (%d)\n", whichq);
1622: }
1623:
1624: simple_lock(&rq->lock); /* lock the run queue */
1625: assert(thread->runq == RUN_QUEUE_NULL);
1626: if (tail)
1627: enqueue_tail(&rq->runq[whichq], (queue_entry_t)thread);
1628: else
1629: enqueue_head(&rq->runq[whichq], (queue_entry_t)thread);
1630:
1631: setbit(MAXPRI - whichq, rq->bitmap);
1632: if (whichq > rq->highq) {
1633: rq->highq = whichq;
1634: }
1635: oldrqcount = rq->count++;
1636: if (whichq == DEPRESSPRI)
1637: rq->depress_count++;
1638: thread->runq = rq;
1639: thread->whichq = whichq;
1640: #if DEBUG
1641: thread_check(thread, rq);
1642: #endif /* DEBUG */
1643: simple_unlock(&rq->lock);
1644:
1645: return (oldrqcount);
1646: }
1647:
1648: /*
1649: * thread_setrun:
1650: *
1651: * Make thread runnable; dispatch directly onto an idle processor
1652: * if possible. Else put on appropriate run queue (processor
1653: * if bound, else processor set. Caller must have lock on thread.
1654: * This is always called at splsched.
1655: * The tail parameter, if TRUE || TAIL_Q, indicates that the
1656: * thread should be placed at the tail of the runq. If
1657: * FALSE || HEAD_Q the thread will be placed at the head of the
1658: * appropriate runq.
1659: */
1660: void
1661: thread_setrun(
1662: register thread_t new_thread,
1663: boolean_t may_preempt,
1664: boolean_t tail)
1665: {
1666: register processor_t processor;
1667: register run_queue_t runq;
1668: register processor_set_t pset;
1669: thread_t thread;
1670: ast_t ast_flags = AST_BLOCK;
1671:
1672: mp_disable_preemption();
1673:
1674: assert(!(new_thread->state & TH_SWAPPED_OUT));
1675: assert(thread_runnable(new_thread));
1676:
1677: /*
1678: * Update priority if needed.
1679: */
1680: /*** ??? fix me ***/
1681: if (new_thread->policy & (POLICY_TIMESHARE|POLICY_RR|POLICY_FIFO)) {
1682: mk_sp_info_t sp_info = new_thread->sp_info;
1683:
1684: assert(sp_info != SP_INFO_NULL);
1685: if (sp_info->sched_stamp != sched_tick)
1686: update_priority(new_thread);
1687:
1688: #if 0 /* TEMPORARILY DISABLE PREEMPTION */
1689: if ( (new_thread->policy & (POLICY_FIFO|POLICY_RR)) &&
1690: sp_info->priority > BASEPRI_SYSTEM )
1691: ast_flags |= AST_URGENT;
1692: #endif /* TEMPORARILY DISABLE PREEMPTION */
1693: }
1694:
1695: assert(new_thread->runq == RUN_QUEUE_NULL);
1696:
1697: /*** ??? fix me ***/
1698: assert(new_thread->sp_info != SP_INFO_NULL);
1699:
1700: /*
1701: * Try to dispatch the thread directly onto an idle processor.
1702: */
1703: if ((processor = new_thread->bound_processor) == PROCESSOR_NULL) {
1704: /*
1705: * Not bound, any processor in the processor set is ok.
1706: */
1707: pset = new_thread->processor_set;
1708: if (pset->idle_count > 0) {
1709: simple_lock(&pset->idle_lock);
1710: if (pset->idle_count > 0) {
1711: processor = (processor_t) queue_first(&pset->idle_queue);
1712: queue_remove(&(pset->idle_queue), processor, processor_t,
1713: processor_queue);
1714: pset->idle_count--;
1715: processor->next_thread = new_thread;
1716: processor->state = PROCESSOR_DISPATCHING;
1717: simple_unlock(&pset->idle_lock);
1718:
1719: mp_enable_preemption();
1720: return;
1721: }
1722: simple_unlock(&pset->idle_lock);
1723: }
1724:
1725:
1726: /*
1727: * Preempt check
1728: */
1729: runq = &pset->runq;
1730: thread = current_thread();
1731: processor = current_processor();
1732: if ( may_preempt &&
1733: #if MACH_HOST
1734: pset == processor->processor_set &&
1735: #endif /* MACH_HOST */
1736: thread->sched_pri < new_thread->sched_pri ) {
1737: simple_lock(&processor->lock);
1738: pset = processor->processor_set;
1739: simple_lock(&pset->idle_lock);
1740:
1741: /*
1742: * XXX if we have a non-empty local runq or are
1743: * XXX running a bound thread, ought to check for
1744: * XXX another cpu running lower-pri thread to preempt.
1745: *
1746: * Turn off first_quantum to allow csw.
1747: */
1748: if (processor->state == PROCESSOR_DISPATCHING) {
1749: thread = processor->next_thread;
1750: processor->next_thread = new_thread;
1751: simple_unlock(&pset->idle_lock);
1752: simple_unlock(&processor->lock);
1753: new_thread = thread;
1754: }
1755: else {
1756: simple_unlock(&pset->idle_lock);
1757: simple_unlock(&processor->lock);
1758: processor->first_quantum = FALSE;
1759: ast_on(ast_flags);
1760: }
1761: }
1762:
1763: /*
1764: * Put us on the end of the runq, if we are not preempting
1765: * or the guy we are preempting.
1766: */
1767: run_queue_enqueue(runq, new_thread, tail);
1768: }
1769: else {
1770: /*
1771: * Bound, can only run on bound processor. Have to lock
1772: * processor here because it may not be the current one.
1773: */
1774: if (processor->state == PROCESSOR_IDLE) {
1775: simple_lock(&processor->lock);
1776: pset = processor->processor_set;
1777: simple_lock(&pset->idle_lock);
1778: if (processor->state == PROCESSOR_IDLE) {
1779: queue_remove(&pset->idle_queue, processor,
1780: processor_t, processor_queue);
1781: pset->idle_count--;
1782: processor->next_thread = new_thread;
1783: processor->state = PROCESSOR_DISPATCHING;
1784: simple_unlock(&pset->idle_lock);
1785: simple_unlock(&processor->lock);
1786:
1787: mp_enable_preemption();
1788: return;
1789: }
1790: simple_unlock(&pset->idle_lock);
1791: simple_unlock(&processor->lock);
1792: }
1793:
1794: /*
1795: * Cause ast on processor if processor is on line, and the
1796: * currently executing thread is not bound to that processor
1797: * (bound threads have implicit priority over non-bound threads).
1798: * We also avoid sending the AST to the idle thread (if it got
1799: * scheduled in the window between the 'if' above and here),
1800: * since the idle_thread is bound.
1801: */
1802: runq = &processor->runq;
1803: thread = current_thread();
1804: if (processor == current_processor()) {
1805: if ( thread->bound_processor == PROCESSOR_NULL ||
1806: thread->sched_pri > new_thread->sched_pri ) {
1807: if (processor->state == PROCESSOR_DISPATCHING) {
1808: thread = processor->next_thread;
1809: processor->next_thread = new_thread;
1810: new_thread = thread;
1811: }
1812: else {
1813: processor->first_quantum = FALSE;
1814: ast_on(ast_flags);
1815: }
1816: }
1817:
1818: run_queue_enqueue(runq, new_thread, tail);
1819: }
1820: else {
1821: thread = cpu_data[processor->slot_num].active_thread;
1822: if ( run_queue_enqueue(runq, new_thread, tail) == 0 &&
1823: processor->state != PROCESSOR_OFF_LINE &&
1824: thread && thread->bound_processor != processor )
1825: cause_ast_check(processor);
1826: }
1827: }
1828:
1829: mp_enable_preemption();
1830: }
1831:
1832: /*
1833: * set_pri:
1834: *
1835: * Set the priority of the specified thread to the specified
1836: * priority. This may cause the thread to change queues.
1837: *
1838: * The thread *must* be locked by the caller.
1839: */
1840: void
1841: set_pri(
1842: thread_t thread,
1843: int pri,
1844: boolean_t resched)
1845: {
1846: register struct run_queue *rq;
1847:
1848: rq = rem_runq(thread);
1849: assert(thread->runq == RUN_QUEUE_NULL);
1850: thread->sched_pri = pri;
1851: if (rq != RUN_QUEUE_NULL) {
1852: if (resched)
1853: thread_setrun(thread, TRUE, TAIL_Q);
1854: else
1855: run_queue_enqueue(rq, thread, TAIL_Q);
1856: }
1857: }
1858:
1859: /*
1860: * rem_runq:
1861: *
1862: * Remove a thread from its run queue.
1863: * The run queue that the process was on is returned
1864: * (or RUN_QUEUE_NULL if not on a run queue). Thread *must* be locked
1865: * before calling this routine. Unusual locking protocol on runq
1866: * field in thread structure makes this code interesting; see thread.h.
1867: */
1868: run_queue_t
1869: rem_runq(
1870: thread_t thread)
1871: {
1872: register struct run_queue *rq;
1873:
1874: rq = thread->runq;
1875: /*
1876: * If rq is RUN_QUEUE_NULL, the thread will stay out of the
1877: * run_queues because the caller locked the thread. Otherwise
1878: * the thread is on a runq, but could leave.
1879: */
1880: if (rq != RUN_QUEUE_NULL) {
1881: #if DEBUG
1882: thread_t t;
1883: int whichq;
1884: #endif
1885: simple_lock(&rq->lock);
1886: if (rq == thread->runq) {
1887: /*
1888: * Thread is in a runq and we have a lock on
1889: * that runq.
1890: */
1891: #if DEBUG
1892: thread_check(thread, rq);
1893: #endif /* DEBUG */
1894: remqueue(&rq->runq[0], (queue_entry_t)thread);
1895: rq->count--;
1896:
1897: if (thread->whichq == DEPRESSPRI)
1898: rq->depress_count--;
1899:
1900: if (queue_empty(rq->runq + thread->sched_pri)) {
1901: /* update run queue status */
1902: clrbit(MAXPRI - thread->sched_pri, rq->bitmap);
1903: rq->highq = MAXPRI - ffsbit(rq->bitmap);
1904: }
1905: thread->runq = RUN_QUEUE_NULL;
1906: simple_unlock(&rq->lock);
1907: }
1908: else {
1909: /*
1910: * The thread left the runq before we could
1911: * lock the runq. It is not on a runq now, and
1912: * can't move again because this routine's
1913: * caller locked the thread.
1914: */
1915: assert(thread->runq == RUN_QUEUE_NULL);
1916: simple_unlock(&rq->lock);
1917: rq = RUN_QUEUE_NULL;
1918: }
1919: }
1920:
1921: return (rq);
1922: }
1923:
1924:
1925: /*
1926: * choose_thread:
1927: *
1928: * Choose a thread to execute. The thread chosen is removed
1929: * from its run queue. Note that this requires only that the runq
1930: * lock be held.
1931: *
1932: * Strategy:
1933: * Check processor runq first; if anything found, run it.
1934: * Else check pset runq; if nothing found, return idle thread.
1935: *
1936: * Second line of strategy is implemented by choose_pset_thread.
1937: * This is only called on processor startup and when thread_block
1938: * thinks there's something in the processor runq.
1939: */
1940: thread_t
1941: choose_thread(
1942: processor_t myprocessor)
1943: {
1944: thread_t thread;
1945: register queue_t q;
1946: register run_queue_t runq;
1947: processor_set_t pset;
1948:
1949: runq = &myprocessor->runq;
1950: pset = myprocessor->processor_set;
1951:
1952: simple_lock(&runq->lock);
1953: if (runq->count > 0 && runq->highq >= pset->runq.highq) {
1954: q = runq->runq + runq->highq;
1955: #if MACH_ASSERT
1956: if (!queue_empty(q)) {
1957: #endif /*MACH_ASSERT*/
1958: thread = (thread_t)q->next;
1959: ((queue_entry_t)thread)->next->prev = q;
1960: q->next = ((queue_entry_t)thread)->next;
1961: thread->runq = RUN_QUEUE_NULL;
1962: runq->count--;
1963: if (thread->whichq == DEPRESSPRI)
1964: runq->depress_count--;
1965: if (queue_empty(q)) {
1966: clrbit(MAXPRI - runq->highq, runq->bitmap);
1967: runq->highq = MAXPRI - ffsbit(runq->bitmap);
1968: }
1969: simple_unlock(&runq->lock);
1970: return (thread);
1971: #if MACH_ASSERT
1972: }
1973: panic("choose_thread");
1974: #endif /*MACH_ASSERT*/
1975: /*NOTREACHED*/
1976: }
1977:
1978: simple_unlock(&runq->lock);
1979: simple_lock(&pset->runq.lock);
1980: return (choose_pset_thread(myprocessor, pset));
1981: }
1982:
1983:
1984: /*
1985: * choose_pset_thread: choose a thread from processor_set runq or
1986: * set processor idle and choose its idle thread.
1987: *
1988: * Caller must be at splsched and have a lock on the runq. This
1989: * lock is released by this routine. myprocessor is always the current
1990: * processor, and pset must be its processor set.
1991: * This routine chooses and removes a thread from the runq if there
1992: * is one (and returns it), else it sets the processor idle and
1993: * returns its idle thread.
1994: */
1995: thread_t
1996: choose_pset_thread(
1997: register processor_t myprocessor,
1998: processor_set_t pset)
1999: {
2000: register run_queue_t runq;
2001: register thread_t thread;
2002: register queue_t q;
2003:
2004: runq = &pset->runq;
2005: if (runq->count > 0) {
2006: q = runq->runq + runq->highq;
2007: #if MACH_ASSERT
2008: if (!queue_empty(q)) {
2009: #endif /*MACH_ASSERT*/
2010: thread = (thread_t)q->next;
2011: ((queue_entry_t)thread)->next->prev = q;
2012: q->next = ((queue_entry_t)thread)->next;
2013: thread->runq = RUN_QUEUE_NULL;
2014: runq->count--;
2015: if (thread->whichq == DEPRESSPRI)
2016: runq->depress_count--;
2017: if (queue_empty(q)) {
2018: clrbit(MAXPRI - runq->highq, runq->bitmap);
2019: runq->highq = MAXPRI - ffsbit(runq->bitmap);
2020: }
2021: simple_unlock(&runq->lock);
2022: return (thread);
2023: #if MACH_ASSERT
2024: }
2025: panic("choose_pset_thread");
2026: #endif /*MACH_ASSERT*/
2027: /*NOTREACHED*/
2028: }
2029: simple_unlock(&runq->lock);
2030:
2031: /*
2032: * Nothing is runnable, so set this processor idle if it
2033: * was running. If it was in an assignment or shutdown,
2034: * leave it alone. Return its idle thread.
2035: */
2036: simple_lock(&pset->idle_lock);
2037: if (myprocessor->state == PROCESSOR_RUNNING) {
2038: myprocessor->state = PROCESSOR_IDLE;
2039: /*
2040: * XXX Until it goes away, put master on end of queue, others
2041: * XXX on front so master gets used last.
2042: */
2043: if (myprocessor == master_processor)
2044: queue_enter(&(pset->idle_queue), myprocessor,
2045: processor_t, processor_queue);
2046: else
2047: queue_enter_first(&(pset->idle_queue), myprocessor,
2048: processor_t, processor_queue);
2049:
2050: pset->idle_count++;
2051: }
2052: simple_unlock(&pset->idle_lock);
2053:
2054: return (myprocessor->idle_thread);
2055: }
2056:
2057: /*
2058: * no_dispatch_count counts number of times processors go non-idle
2059: * without being dispatched. This should be very rare.
2060: */
2061: int no_dispatch_count = 0;
2062:
2063: /*
2064: * This is the idle thread, which just looks for other threads
2065: * to execute.
2066: */
2067: void
2068: idle_thread_continue(void)
2069: {
2070: register processor_t myprocessor;
2071: register volatile thread_t *threadp;
2072: register volatile int *gcount;
2073: register volatile int *lcount;
2074: register thread_t new_thread;
2075: register int state;
2076: register processor_set_t pset;
2077: int mycpu;
2078: spl_t s;
2079:
2080: mycpu = cpu_number();
2081: myprocessor = current_processor();
2082: threadp = (volatile thread_t *) &myprocessor->next_thread;
2083: lcount = (volatile int *) &myprocessor->runq.count;
2084:
2085: for (;;) {
2086: #ifdef MARK_CPU_IDLE
2087: MARK_CPU_IDLE(mycpu);
2088: #endif /* MARK_CPU_IDLE */
2089:
2090: #if MACH_HOST
2091: gcount = (volatile int *)&myprocessor->processor_set->runq.count;
2092: #else /* MACH_HOST */
2093: gcount = (volatile int *)&default_pset.runq.count;
2094: #endif /* MACH_HOST */
2095:
2096: /*
2097: * This cpu will be dispatched (by thread_setrun) by setting next_thread
2098: * to the value of the thread to run next. Also check runq counts.
2099: */
2100: s = splsched();
2101: while ((*threadp == (volatile thread_t)THREAD_NULL) && (*gcount == 0) && (*lcount == 0)) {
2102:
2103: /* check for ASTs while we wait */
2104:
2105: if (need_ast[mycpu] &~ (AST_SCHEDULING|AST_BSD|AST_BSD_INIT)) {
2106: /* don't allow scheduling ASTs */
2107: need_ast[mycpu] &= ~(AST_SCHEDULING|AST_BSD|AST_BSD_INIT);
2108: splx(s);
2109: ast_taken(FALSE, AST_ALL, s);
2110: /* back at spllo */
2111: }
2112: else
2113: splx(s);
2114:
2115: machine_clock_assist();
2116:
2117: /*
2118: * machine_idle is a machine dependent function,
2119: * to conserve power.
2120: */
2121: #if POWER_SAVE
2122: machine_idle(mycpu);
2123: #endif /* POWER_SAVE */
2124: s = splsched();
2125: }
2126:
2127: #ifdef MARK_CPU_ACTIVE
2128: splx(s);
2129: MARK_CPU_ACTIVE(mycpu);
2130: s = splsched();
2131: #endif /* MARK_CPU_ACTIVE */
2132:
2133: /*
2134: * This is not a switch statement to avoid the
2135: * bounds checking code in the common case.
2136: */
2137: pset = myprocessor->processor_set;
2138: simple_lock(&pset->idle_lock);
2139: retry:
2140: state = myprocessor->state;
2141: if (state == PROCESSOR_DISPATCHING) {
2142: /*
2143: * Commmon case -- cpu dispatched.
2144: */
2145: new_thread = *threadp;
2146: *threadp = (volatile thread_t) THREAD_NULL;
2147: myprocessor->state = PROCESSOR_RUNNING;
2148:
2149: simple_unlock(&pset->idle_lock);
2150: thread_lock(new_thread);
2151:
2152: /*
2153: * set up quantum for new thread.
2154: */
2155: if (new_thread->policy == POLICY_TIMESHARE) {
2156: /*
2157: * Just use set quantum. No point in
2158: * checking for shorter local runq quantum;
2159: * csw_needed will handle correctly.
2160: */
2161: #if MACH_HOST
2162: myprocessor->quantum = new_thread->processor_set->set_quantum;
2163: #else /* MACH_HOST */
2164: myprocessor->quantum = default_pset.set_quantum;
2165: #endif /* MACH_HOST */
2166: }
2167: else
2168: if (new_thread->policy & (POLICY_RR|POLICY_FIFO)) {
2169: mk_sp_info_t sp_info = (mk_sp_info_t)new_thread->sp_info;
2170:
2171: assert(sp_info != SP_INFO_NULL);
2172: myprocessor->quantum = sp_info->unconsumed_quantum;
2173: }
2174:
2175: thread_unlock(new_thread);
2176:
2177: myprocessor->first_quantum = TRUE;
2178: counter(c_idle_thread_handoff++);
2179: thread_run((void(*)(void))0, new_thread);
2180: }
2181: else
2182: if (state == PROCESSOR_IDLE) {
2183:
2184: if (myprocessor->state != PROCESSOR_IDLE) {
2185: /*
2186: * Something happened, try again.
2187: */
2188: goto retry;
2189: }
2190: /*
2191: * Processor was not dispatched (Rare).
2192: * Set it running again.
2193: */
2194: no_dispatch_count++;
2195: pset->idle_count--;
2196: queue_remove(&pset->idle_queue, myprocessor,
2197: processor_t, processor_queue);
2198: myprocessor->state = PROCESSOR_RUNNING;
2199: simple_unlock(&pset->idle_lock);
2200: counter(c_idle_thread_block++);
2201: thread_block((void(*)(void))0);
2202: }
2203: else
2204: if ( state == PROCESSOR_ASSIGN ||
2205: state == PROCESSOR_SHUTDOWN ) {
2206: /*
2207: * Changing processor sets, or going off-line.
2208: * Release next_thread if there is one. Actual
2209: * thread to run in on a runq.
2210: */
2211: if ((new_thread = (thread_t)*threadp)!= THREAD_NULL) {
2212: *threadp = (volatile thread_t) THREAD_NULL;
2213: thread_setrun(new_thread, FALSE, TAIL_Q);
2214: }
2215:
2216: counter(c_idle_thread_block++);
2217: thread_block((void(*)(void))0);
2218: }
2219: else {
2220: simple_unlock(&pset->idle_lock);
2221: printf("Bad processor state %d (Cpu %d)\n",
2222: cpu_state(mycpu), mycpu);
2223: panic("idle_thread");
2224:
2225: }
2226: splx(s);
2227: }
2228: }
2229:
2230: void
2231: idle_thread(void)
2232: {
2233: thread_t self = current_thread();
2234: mk_sp_info_t sp_info;
2235: spl_t s;
2236:
2237: stack_privilege(self);
2238: thread_swappable(current_act(), FALSE);
2239:
2240: s = splsched();
2241: thread_lock(self);
2242:
2243: /*
2244: * Set the idle flag to indicate that this is an idle thread,
2245: * enter ourselves in the idle array, and thread_block() to get
2246: * out of the run queues (and set the processor idle when we
2247: * run next time).
2248: */
2249: self->state |= TH_IDLE;
2250: current_processor()->idle_thread = self;
2251:
2252: /*** ??? fix me ***/
2253: assert(self->policy == POLICY_FIFO);
2254: sp_info = (mk_sp_info_t)self->sp_info;
2255: assert(sp_info != SP_INFO_NULL);
2256: sp_info->priority = IDLEPRI;
2257: self->sched_pri = sp_info->priority;
2258:
2259: thread_unlock(self);
2260: splx(s);
2261:
2262: counter(c_idle_thread_block++);
2263: thread_block((void(*)(void))0);
2264: idle_thread_continue();
2265: /*NOTREACHED*/
2266:
2267: panic("idle_thread_continue!");
2268: }
2269:
2270: static thread_call_t sched_tick_timer;
2271: static thread_call_data_t sched_tick_timer_data;
2272: static AbsoluteTime sched_tick_interval, sched_tick_deadline;
2273:
2274: /*
2275: * recompute_priorities:
2276: *
2277: * Update the priorities of all threads periodically.
2278: */
2279: void
2280: _recompute_priorities(void)
2281: {
2282: AbsoluteTime abstime;
2283: #if SIMPLE_CLOCK
2284: int new_usec;
2285: #endif /* SIMPLE_CLOCK */
2286:
2287: clock_get_uptime(&abstime);
2288:
2289: sched_tick++; /* age usage one more time */
2290: #if SIMPLE_CLOCK
2291: /*
2292: * Compensate for clock drift. sched_usec is an
2293: * exponential average of the number of microseconds in
2294: * a second. It decays in the same fashion as cpu_usage.
2295: */
2296: new_usec = sched_usec_elapsed();
2297: sched_usec = (5*sched_usec + 3*new_usec)/8;
2298: #endif /* SIMPLE_CLOCK */
2299:
2300: /*
2301: * Compute the scheduler load factors.
2302: */
2303: compute_mach_factor();
2304:
2305: /*
2306: * Scan the run queues for runnable threads that need to
2307: * have their priorities recalculated.
2308: */
2309: do_thread_scan();
2310:
2311: clock_deadline_for_periodic_event(sched_tick_interval, abstime,
2312: &sched_tick_deadline);
2313: thread_call_enter_delayed(sched_tick_timer, sched_tick_deadline);
2314: }
2315:
2316: void
2317: recompute_priorities(void)
2318: {
2319: thread_call_setup(&sched_tick_timer_data, _recompute_priorities, NULL);
2320: clock_interval_to_absolutetime_interval(1, NSEC_PER_SEC,
2321: &sched_tick_interval);
2322: clock_get_uptime(&sched_tick_deadline);
2323: sched_tick_timer = &sched_tick_timer_data;
2324:
2325: _recompute_priorities();
2326: }
2327:
2328: #define MAX_STUCK_THREADS 128
2329:
2330: /*
2331: * do_thread_scan: scan for stuck threads. A thread is stuck if
2332: * it is runnable but its priority is so low that it has not
2333: * run for several seconds. Its priority should be higher, but
2334: * won't be until it runs and calls update_priority. The scanner
2335: * finds these threads and does the updates.
2336: *
2337: * Scanner runs in two passes. Pass one squirrels likely
2338: * thread ids away in an array (takes out references for them).
2339: * Pass two does the priority updates. This is necessary because
2340: * the run queue lock is required for the candidate scan, but
2341: * cannot be held during updates [set_pri will deadlock].
2342: *
2343: * Array length should be enough so that restart isn't necessary,
2344: * but restart logic is included. Does not scan processor runqs.
2345: *
2346: */
2347: thread_t stuck_threads[MAX_STUCK_THREADS];
2348: int stuck_count = 0;
2349:
2350: /*
2351: * do_runq_scan is the guts of pass 1. It scans a runq for
2352: * stuck threads. A boolean is returned indicating whether
2353: * a retry is needed.
2354: */
2355: boolean_t
2356: do_runq_scan(
2357: run_queue_t runq,
2358: int *mask)
2359: {
2360: register queue_t q;
2361: register thread_t thread;
2362: register int count;
2363: int qindex;
2364: spl_t s;
2365: boolean_t result = FALSE;
2366:
2367: s = splsched();
2368: simple_lock(&runq->lock);
2369: if ((count = runq->count) > 0) {
2370: q = runq->runq + runq->highq;
2371: qindex = runq->highq;
2372: while (count > 0) {
2373: boolean_t qvalid = testbit(qindex, mask);
2374:
2375: queue_iterate(q, thread, thread_t, links) {
2376: if ( qvalid &&
2377: !(thread->state & (TH_WAIT|TH_SUSP)) &&
2378: thread->policy == POLICY_TIMESHARE ) {
2379: mk_sp_info_t sp_info = thread->sp_info;
2380:
2381: assert(sp_info != SP_INFO_NULL);
2382: /*** ??? fix me ***/
2383: if (sp_info->sched_stamp != sched_tick) {
2384: /*
2385: * Stuck, save its id for later.
2386: */
2387: if (stuck_count == MAX_STUCK_THREADS) {
2388: /*
2389: * !@#$% No more room.
2390: */
2391: simple_unlock(&runq->lock);
2392: splx(s);
2393:
2394: return (TRUE);
2395: }
2396:
2397: /*
2398: * Inline version of thread_reference
2399: * XXX - lock ordering problem here:
2400: * thread locks should be taken before runq
2401: * locks: just try and get the thread's locks
2402: * and ignore this thread if we fail, we might
2403: * have better luck next time.
2404: */
2405: if (simple_lock_try(&thread->lock)) {
2406: thread->ref_count++;
2407: thread_unlock(thread);
2408: stuck_threads[stuck_count++] = thread;
2409: }
2410: else
2411: result = TRUE;
2412: }
2413: }
2414:
2415: count--;
2416: }
2417:
2418: q--;
2419: qindex--;
2420: }
2421: }
2422: simple_unlock(&runq->lock);
2423: splx(s);
2424:
2425: return (result);
2426: }
2427:
2428: boolean_t thread_scan_enabled = TRUE;
2429:
2430: void
2431: do_thread_scan(void)
2432: {
2433: register boolean_t restart_needed = FALSE;
2434: register thread_t thread;
2435: #if MACH_HOST
2436: register processor_set_t pset;
2437: #endif /* MACH_HOST */
2438: int *mask;
2439: spl_t s;
2440:
2441: if (!thread_scan_enabled)
2442: return;
2443:
2444: mask = sched_policy[POLICY_TIMESHARE].priority_mask.bitmap;
2445:
2446: do {
2447: #if MACH_HOST
2448: mutex_lock(&all_psets_lock);
2449: queue_iterate(&all_psets, pset, processor_set_t, all_psets) {
2450: if (restart_needed = do_runq_scan(&pset->runq, mask))
2451: break;
2452: }
2453: mutex_unlock(&all_psets_lock);
2454: #else /* MACH_HOST */
2455: restart_needed = do_runq_scan(&default_pset.runq, mask);
2456: #endif /* MACH_HOST */
2457: if (!restart_needed)
2458: restart_needed = do_runq_scan(&master_processor->runq, mask);
2459:
2460: /*
2461: * Ok, we now have a collection of candidates -- fix them.
2462: */
2463: while (stuck_count > 0) {
2464: thread = stuck_threads[--stuck_count];
2465: stuck_threads[stuck_count] = THREAD_NULL;
2466: s = splsched();
2467: thread_lock(thread);
2468: /*** ??? fix me ***/
2469: if (thread->policy == POLICY_TIMESHARE) {
2470: mk_sp_info_t sp_info = thread->sp_info;
2471:
2472: assert(thread->sp_info != SP_INFO_NULL);
2473: if ( !(thread->state & (TH_WAIT|TH_SUSP)) &&
2474: /*** ??? fix me ***/
2475: sp_info->sched_stamp != sched_tick )
2476: update_priority(thread);
2477: }
2478: thread_unlock(thread);
2479: splx(s);
2480: thread_deallocate(thread);
2481: }
2482:
2483: } while (restart_needed);
2484: }
2485:
2486: /*
2487: * Just in case someone doesn't use the macro
2488: */
2489: #undef thread_wakeup
2490: void
2491: thread_wakeup(
2492: event_t x);
2493:
2494: void
2495: thread_wakeup(
2496: event_t x)
2497: {
2498: thread_wakeup_with_result(x, THREAD_AWAKENED);
2499: }
2500:
2501: boolean_t
2502: thread_runnable(
2503: thread_t thread)
2504: {
2505: sched_policy_t *policy;
2506:
2507: /* Ask sched policy if thread is runnable */
2508: policy = policy_id_to_sched_policy(thread->policy);
2509:
2510: return ((policy != SCHED_POLICY_NULL)?
2511: policy->sp_ops.sp_thread_runnable(policy, thread) : FALSE);
2512: }
2513:
2514: void
2515: dump_processor_set(
2516: processor_set_t ps)
2517: {
2518: printf("processor_set: %08x\n",ps);
2519: printf("idle_queue: %08x %08x, idle_count: 0x%x\n",
2520: ps->idle_queue.next,ps->idle_queue.prev,ps->idle_count);
2521: printf("processors: %08x %08x, processor_count: 0x%x, empty: %x\n",
2522: ps->processors.next,ps->processors.prev,ps->processor_count);
2523: printf("tasks: %08x %08x, task_count: 0x%x\n",
2524: ps->tasks.next,ps->tasks.prev,ps->task_count);
2525: printf("threads: %08x %08x, thread_count: 0x%x\n",
2526: ps->threads.next,ps->threads.prev,ps->thread_count);
2527: printf("ref_count: 0x%x, all_psets: %08x %08x, active: %x\n",
2528: ps->ref_count, ps->all_psets.next,ps->all_psets.prev,ps->active);
2529: printf("pset_self: %08x, pset_name_self: %08x\n",ps->pset_self, ps->pset_name_self);
2530: printf("max_priority: 0x%x, policies: 0x%x, set_quantum: 0x%x\n",
2531: ps->max_priority, ps->policies, ps->set_quantum);
2532: }
2533:
2534: #define processor_state(s) (((s)>PROCESSOR_SHUTDOWN)?"*unknown*":states[s])
2535:
2536: void
2537: dump_processor(
2538: processor_t p)
2539: {
2540: char *states[]={"OFF_LINE","RUNNING","IDLE","DISPATCHING",
2541: "ASSIGN","SHUTDOWN"};
2542:
2543: printf("processor: %08x\n",p);
2544: printf("processor_queue: %08x %08x\n",
2545: p->processor_queue.next,p->processor_queue.prev);
2546: printf("state: %8s, next_thread: %08x, idle_thread: %08x\n",
2547: processor_state(p->state), p->next_thread, p->idle_thread);
2548: printf("quantum: %u, first_quantum: %x, last_quantum: %u\n",
2549: p->quantum, p->first_quantum, p->last_quantum);
2550: printf("processor_set: %08x, processor_set_next: %08x\n",
2551: p->processor_set, p->processor_set_next);
2552: printf("processors: %08x %08x\n", p->processors.next,p->processors.prev);
2553: printf("processor_self: %08x, slot_num: 0x%x\n", p->processor_self, p->slot_num);
2554: }
2555:
2556: void
2557: dump_run_queue_struct(
2558: run_queue_t rq)
2559: {
2560: char dump_buf[80];
2561: int i;
2562:
2563: for( i=0; i < NRQS; ) {
2564: int j;
2565:
2566: printf("%6s",(i==0)?"runq:":"");
2567: for( j=0; (j<8) && (i < NRQS); j++,i++ ) {
2568: if( rq->runq[i].next == &rq->runq[i] )
2569: printf( " --------");
2570: else
2571: printf(" %08x",rq->runq[i].next);
2572: }
2573: printf("\n");
2574: }
2575: for( i=0; i < NRQBM; ) {
2576: register unsigned int mask;
2577: char *d=dump_buf;
2578:
2579: mask = ~0;
2580: mask ^= (mask>>1);
2581:
2582: do {
2583: *d++ = ((rq->bitmap[i]&mask)?'r':'e');
2584: mask >>=1;
2585: } while( mask );
2586: *d = '\0';
2587: printf("%8s%s\n",((i==0)?"bitmap:":""),dump_buf);
2588: i++;
2589: }
2590: printf("highq: 0x%x, count: %u\n", rq->highq, rq->count);
2591: }
2592:
2593: void
2594: dump_run_queues(
2595: run_queue_t runq)
2596: {
2597: register queue_t q1;
2598: register int i;
2599: register queue_entry_t e;
2600:
2601: q1 = runq->runq;
2602: for (i = 0; i < NRQS; i++) {
2603: if (q1->next != q1) {
2604: int t_cnt;
2605:
2606: printf("[%u]",i);
2607: for (t_cnt=0, e = q1->next; e != q1; e = e->next) {
2608: printf("\t0x%08x",e);
2609: if( (t_cnt = ++t_cnt%4) == 0 )
2610: printf("\n");
2611: }
2612: if( t_cnt )
2613: printf("\n");
2614: }
2615: /* else
2616: printf("[%u]\t<empty>\n",i);
2617: */
2618: q1++;
2619: }
2620: }
2621:
2622: #if DEBUG
2623:
2624: void
2625: checkrq(
2626: run_queue_t rq,
2627: char *msg)
2628: {
2629: register queue_t q1;
2630: register int i, j;
2631: register queue_entry_t e;
2632: register int highq;
2633:
2634: highq = NRQS;
2635: j = 0;
2636: q1 = rq->runq;
2637: for (i = MAXPRI; i >= 0; i--) {
2638: if (q1->next == q1) {
2639: if (q1->prev != q1) {
2640: panic("checkrq: empty at %s", msg);
2641: }
2642: }
2643: else {
2644: if (highq == -1)
2645: highq = i;
2646:
2647: for (e = q1->next; e != q1; e = e->next) {
2648: j++;
2649: if (e->next->prev != e)
2650: panic("checkrq-2 at %s", msg);
2651: if (e->prev->next != e)
2652: panic("checkrq-3 at %s", msg);
2653: }
2654: }
2655: q1++;
2656: }
2657: if (j != rq->count)
2658: panic("checkrq: count wrong at %s", msg);
2659: if (rq->count != 0 && highq > rq->highq)
2660: panic("checkrq: highq wrong at %s", msg);
2661: }
2662:
2663: void
2664: thread_check(
2665: register thread_t th,
2666: register run_queue_t rq)
2667: {
2668: register unsigned int whichq;
2669:
2670: whichq = th->sched_pri;
2671: if (whichq < MINPRI) {
2672: printf("thread_check: priority too high\n");
2673: whichq = MINPRI;
2674: }
2675: if ((th->links.next == &rq->runq[whichq]) &&
2676: (rq->runq[whichq].prev != (queue_entry_t)th))
2677: panic("thread_check");
2678: }
2679:
2680: #endif /* DEBUG */
2681:
2682: #if MACH_KDB
2683: #include <ddb/db_output.h>
2684: #define printf kdbprintf
2685: extern int db_indent;
2686: void db_sched(void);
2687:
2688: void
2689: db_sched(void)
2690: {
2691: iprintf("Scheduling Statistics:\n");
2692: db_indent += 2;
2693: iprintf("Thread invocations: csw %d same %d\n",
2694: c_thread_invoke_csw, c_thread_invoke_same);
2695: #if MACH_COUNTERS
2696: iprintf("Thread block: calls %d\n",
2697: c_thread_block_calls);
2698: iprintf("Idle thread:\n\thandoff %d block %d no_dispatch %d\n",
2699: c_idle_thread_handoff,
2700: c_idle_thread_block, no_dispatch_count);
2701: iprintf("Sched thread blocks: %d\n", c_sched_thread_block);
2702: #endif /* MACH_COUNTERS */
2703: db_indent -= 2;
2704: }
2705: #endif /* MACH_KDB */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.