Return to sched_prim.c CVS log

Up to [Apple XNU] / XNU / osfmk / kern

Annotation of XNU/osfmk/kern/sched_prim.c, revision 1.1

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.