Return to task_swap.c CVS log

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

Annotation of XNU/osfmk/kern/task_swap.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_COPYRIGHT@
        !            24:  */
        !            25: /*      
        !            26:  *             File:   kern/task_swap.c
        !            27:  *      
        !            28:  *     Task residency management primitives implementation.
        !            29:  */
        !            30: #include <mach_assert.h>
        !            31: #include <task_swapper.h>
        !            32: 
        !            33: #include <kern/spl.h>
        !            34: #include <kern/lock.h>
        !            35: #include <kern/queue.h>
        !            36: #include <kern/host.h>
        !            37: #include <kern/task.h>
        !            38: #include <kern/task_swap.h>
        !            39: #include <kern/thread.h>
        !            40: #include <kern/thread_swap.h>
        !            41: #include <kern/host_statistics.h>
        !            42: #include <kern/misc_protos.h>
        !            43: #include <kern/assert.h>
        !            44: #include <mach/policy.h>
        !            45: 
        !            46: #include <ipc/ipc_port.h>      /* We use something from in here */
        !            47: 
        !            48: /*
        !            49:  * Note:  if TASK_SWAPPER is disabled, then this file defines only
        !            50:  * a stub version of task_swappable(), so that the service can always
        !            51:  * be defined, even if swapping has been configured out of the kernel.
        !            52:  */
        !            53: #if TASK_SWAPPER
        !            54: 
        !            55: /* temporary debug flags */
        !            56: #define TASK_SW_DEBUG 1
        !            57: #define TASK_SW_STATS 1
        !            58: 
        !            59: int task_swap_debug = 0;
        !            60: int task_swap_stats = 0;
        !            61: int task_swap_enable = 1;
        !            62: int task_swap_on = 1;
        !            63: 
        !            64: queue_head_t   swapped_tasks;          /* completely swapped out tasks */
        !            65: queue_head_t   swapout_thread_q;       /* threads to be swapped out */
        !            66: mutex_t                task_swapper_lock;      /* protects above queue */
        !            67: 
        !            68: #define task_swapper_lock()    mutex_lock(&task_swapper_lock)
        !            69: #define task_swapper_unlock()  mutex_unlock(&task_swapper_lock)
        !            70: 
        !            71: queue_head_t   eligible_tasks;         /* tasks eligible for swapout */
        !            72: mutex_t                task_swapout_list_lock; /* protects above queue */
        !            73: #define task_swapout_lock()    mutex_lock(&task_swapout_list_lock)
        !            74: #define task_swapout_unlock()  mutex_unlock(&task_swapout_list_lock)
        !            75: 
        !            76: /*
        !            77:  * The next section of constants and globals are tunable parameters
        !            78:  * used in making swapping decisions.  They may be changed dynamically
        !            79:  * without adversely affecting the robustness of the system; however,
        !            80:  * the policy will change, one way or the other.
        !            81:  */
        !            82: 
        !            83: #define SHORT_AVG_INTERVAL     5       /* in seconds */
        !            84: #define LONG_AVG_INTERVAL      30      /* in seconds */
        !            85: #define AVE_SCALE              1024
        !            86: 
        !            87: unsigned int short_avg_interval = SHORT_AVG_INTERVAL;
        !            88: unsigned int long_avg_interval = LONG_AVG_INTERVAL;
        !            89: 
        !            90: #ifndef MIN_SWAP_PAGEOUT_RATE
        !            91: #define MIN_SWAP_PAGEOUT_RATE  10
        !            92: #endif
        !            93: 
        !            94: /*
        !            95:  * The following are all stored in fixed-point representation (the actual
        !            96:  * value times AVE_SCALE), to allow more accurate computing of decaying
        !            97:  * averages.  So all variables that end with "avg" must be divided by
        !            98:  * AVE_SCALE to convert them or compare them to ints.
        !            99:  */
        !           100: unsigned int vm_grab_rate_avg;
        !           101: unsigned int vm_pageout_rate_avg = MIN_SWAP_PAGEOUT_RATE * AVE_SCALE;
        !           102: unsigned int vm_pageout_rate_longavg = MIN_SWAP_PAGEOUT_RATE * AVE_SCALE;
        !           103: unsigned int vm_pageout_rate_peakavg = MIN_SWAP_PAGEOUT_RATE * AVE_SCALE;
        !           104: unsigned int vm_page_free_avg; /* average free pages over short_avg_interval */
        !           105: unsigned int vm_page_free_longavg; /* avg free pages over long_avg_interval */
        !           106: 
        !           107: /*
        !           108:  * Trigger task swapping when paging activity reaches
        !           109:  * SWAP_HIGH_WATER_MARK per cent of the maximum paging activity ever observed.
        !           110:  * Turn off task swapping when paging activity goes back down to below
        !           111:  * SWAP_PAGEOUT_LOW_WATER_MARK per cent of the maximum.
        !           112:  * These numbers have been found empirically and might need some tuning...
        !           113:  */
        !           114: #ifndef SWAP_PAGEOUT_HIGH_WATER_MARK
        !           115: #define SWAP_PAGEOUT_HIGH_WATER_MARK   30
        !           116: #endif
        !           117: #ifndef SWAP_PAGEOUT_LOW_WATER_MARK
        !           118: #define SWAP_PAGEOUT_LOW_WATER_MARK    10
        !           119: #endif
        !           120: 
        !           121: #ifndef MAX_GRAB_RATE
        !           122: #define MAX_GRAB_RATE  ((unsigned int) -1)     /* XXX no maximum */
        !           123: #endif
        !           124: 
        !           125: /*
        !           126:  * swap_{start,stop}_pageout_rate start at the minimum value, then increase
        !           127:  * to adjust to the hardware's performance, following the paging rate peaks.
        !           128:  */
        !           129: unsigned int swap_pageout_high_water_mark = SWAP_PAGEOUT_HIGH_WATER_MARK;
        !           130: unsigned int swap_pageout_low_water_mark = SWAP_PAGEOUT_LOW_WATER_MARK;
        !           131: unsigned int swap_start_pageout_rate = MIN_SWAP_PAGEOUT_RATE * AVE_SCALE *
        !           132:                                        SWAP_PAGEOUT_HIGH_WATER_MARK / 100;
        !           133: unsigned int swap_stop_pageout_rate = MIN_SWAP_PAGEOUT_RATE * AVE_SCALE *
        !           134:                                        SWAP_PAGEOUT_LOW_WATER_MARK / 100;
        !           135: #if    TASK_SW_DEBUG
        !           136: unsigned int fixed_swap_start_pageout_rate = 0;        /* only for testing purpose */
        !           137: unsigned int fixed_swap_stop_pageout_rate = 0; /* only for testing purpose */
        !           138: #endif /* TASK_SW_DEBUG */
        !           139: unsigned int max_grab_rate = MAX_GRAB_RATE;
        !           140: 
        !           141: #ifndef MIN_SWAP_TIME
        !           142: #define MIN_SWAP_TIME  1
        !           143: #endif
        !           144: 
        !           145: int min_swap_time = MIN_SWAP_TIME;                     /* in seconds */
        !           146: 
        !           147: #ifndef MIN_RES_TIME
        !           148: #define MIN_RES_TIME   6
        !           149: #endif
        !           150: 
        !           151: int min_res_time = MIN_RES_TIME;                       /* in seconds */
        !           152: 
        !           153: #ifndef MIN_ACTIVE_TASKS
        !           154: #define MIN_ACTIVE_TASKS       4
        !           155: #endif
        !           156: 
        !           157: int min_active_tasks = MIN_ACTIVE_TASKS;
        !           158: 
        !           159: #ifndef TASK_SWAP_CYCLE_TIME
        !           160: #define TASK_SWAP_CYCLE_TIME   2
        !           161: #endif
        !           162: 
        !           163: int task_swap_cycle_time = TASK_SWAP_CYCLE_TIME;       /* in seconds */
        !           164: 
        !           165: int last_task_swap_cycle = 0;
        !           166: 
        !           167: /* temporary statistics */
        !           168: int task_swapouts = 0;
        !           169: int task_swapins = 0;
        !           170: int task_swaprss_out = 0;      /* total rss at swapout time */
        !           171: int task_swaprss_in = 0;       /* total rss at swapin time */
        !           172: int task_swap_total_time = 0;  /* total time spent swapped out */
        !           173: int tasks_swapped_out = 0;     /* number of tasks swapped out now */
        !           174: 
        !           175: #ifdef TASK_SW_STATS
        !           176: #define TASK_STATS_INCR(cnt)   (cnt)++
        !           177: #else
        !           178: #define TASK_STATS_INCR(cnt)
        !           179: #endif /* TASK_SW_STATS */
        !           180: 
        !           181: #if    TASK_SW_DEBUG
        !           182: boolean_t on_swapped_list(task_t task);        /* forward */
        !           183: /*
        !           184:  * Debug function to determine if a task is already on the
        !           185:  * swapped out tasks list.  It also checks for tasks on the list
        !           186:  * that are in an illegal state (i.e. swapped in).
        !           187:  */
        !           188: boolean_t
        !           189: on_swapped_list(task_t task)
        !           190: {
        !           191:        task_t ltask;
        !           192:        /* task_swapper_lock is locked. */
        !           193: 
        !           194:        if (queue_empty(&swapped_tasks)) {
        !           195:                return(FALSE);
        !           196:        }
        !           197:        ltask = (task_t)queue_first(&swapped_tasks);
        !           198:        while (!queue_end(&swapped_tasks, (queue_entry_t)ltask)) {
        !           199:                /* check for illegal state */
        !           200:                if (ltask->swap_state == TASK_SW_IN) {
        !           201:                        printf("on_swapped_list and in: 0x%X\n",ltask);
        !           202:                        Debugger("");
        !           203:                }
        !           204:                if (ltask == task)
        !           205:                        return(TRUE);
        !           206:                ltask = (task_t)queue_next(&ltask->swapped_tasks);
        !           207:        }
        !           208:        return(FALSE);
        !           209: }
        !           210: #endif /* TASK_SW_DEBUG */
        !           211: 
        !           212: /*
        !           213:  *     task_swapper_init: [exported]
        !           214:  */
        !           215: void
        !           216: task_swapper_init()
        !           217: {
        !           218:        queue_init(&swapped_tasks);
        !           219:        queue_init(&eligible_tasks);
        !           220:        queue_init(&swapout_thread_q);
        !           221:        mutex_init(&task_swapper_lock, ETAP_THREAD_TASK_SWAP);
        !           222:        mutex_init(&task_swapout_list_lock, ETAP_THREAD_TASK_SWAPOUT);
        !           223:        vm_page_free_avg = vm_page_free_count * AVE_SCALE;
        !           224:        vm_page_free_longavg = vm_page_free_count * AVE_SCALE;
        !           225: }
        !           226: 
        !           227: #endif /* TASK_SWAPPER */
        !           228: 
        !           229: /*
        !           230:  *     task_swappable: [exported]
        !           231:  *
        !           232:  *     Make a task swappable or non-swappable. If made non-swappable,
        !           233:  *     it will be swapped in.
        !           234:  *
        !           235:  *     Locking: task_swapout_lock is taken before task lock.
        !           236:  */
        !           237: kern_return_t
        !           238: task_swappable(host_t host, task_t task, boolean_t make_swappable)
        !           239: {
        !           240:        if (host == HOST_NULL)
        !           241:                return(KERN_INVALID_ARGUMENT);
        !           242: 
        !           243:        if (task == TASK_NULL)
        !           244:                return(KERN_INVALID_ARGUMENT);
        !           245: 
        !           246: #if    !TASK_SWAPPER
        !           247: 
        !           248:        /*
        !           249:         * If we don't support swapping, this call is purely advisory.
        !           250:         */
        !           251:        return(KERN_SUCCESS);
        !           252: 
        !           253: #else  /* TASK_SWAPPER */
        !           254:        
        !           255:        task_lock(task);
        !           256:        if (make_swappable) {
        !           257:                /* make task swappable */
        !           258:                if (task->swap_state == TASK_SW_UNSWAPPABLE) {
        !           259:                        task->swap_state = TASK_SW_IN; 
        !           260:                        task_unlock(task);
        !           261:                        task_swapout_eligible(task);
        !           262:                }
        !           263:        } else {
        !           264:            switch (task->swap_state) {
        !           265:                case TASK_SW_IN:
        !           266:                        task->swap_state = TASK_SW_UNSWAPPABLE;
        !           267:                        task_unlock(task);
        !           268:                        task_swapout_ineligible(task);
        !           269:                        break;
        !           270:                case TASK_SW_UNSWAPPABLE:
        !           271:                        task_unlock(task);
        !           272:                        break;
        !           273:                default:
        !           274:                        /*
        !           275:                         * swap_state could be TASK_SW_OUT, TASK_SW_GOING_OUT,
        !           276:                         * or TASK_SW_COMING_IN.  task_swapin handles all
        !           277:                         * three, and its default case will catch any bad
        !           278:                         * states.
        !           279:                         */
        !           280:                        task_unlock(task);
        !           281:                        task_swapin(task, TRUE);
        !           282:                        break;
        !           283:            }
        !           284:        }
        !           285:        return(KERN_SUCCESS);
        !           286: 
        !           287: #endif /* TASK_SWAPPER */
        !           288: 
        !           289: }
        !           290: 
        !           291: #if    TASK_SWAPPER
        !           292: 
        !           293: /*
        !           294:  *     task_swapout:
        !           295:  *     A reference to the task must be held.
        !           296:  *
        !           297:  *     Start swapping out a task by sending an AST_SWAPOUT to each thread.
        !           298:  *     When the threads reach a clean point, they queue themselves up on the
        !           299:  *     swapout_thread_q to be swapped out by the task_swap_swapout_thread.
        !           300:  *     The task can be swapped in at any point in this process.
        !           301:  *
        !           302:  *     A task will not be fully swapped out (i.e. its map residence count
        !           303:  *     at zero) until all currently-swapped threads run and reach
        !           304:  *     a clean point, at which time they will be swapped again,
        !           305:  *     decrementing the swap_ast_waiting count on the task.
        !           306:  *
        !           307:  *     Locking: no locks held upon entry and exit.
        !           308:  *              Task_lock is held throughout this function.
        !           309:  */
        !           310: kern_return_t
        !           311: task_swapout(task_t task)
        !           312: {
        !           313:        thread_act_t thr_act;
        !           314:        thread_t thread;
        !           315:        queue_head_t *list;
        !           316:        int s;
        !           317: 
        !           318:        task_swapout_lock();
        !           319:        task_lock(task);
        !           320:        /*
        !           321:         * NOTE: look into turning these into assertions if they
        !           322:         * are invariants.
        !           323:         */
        !           324:        if ((task->swap_state != TASK_SW_IN) || (!task->active)) {
        !           325:                task_unlock(task);
        !           326:                task_swapout_unlock();
        !           327:                return(KERN_FAILURE);
        !           328:        }
        !           329:        if (task->swap_flags & TASK_SW_ELIGIBLE) {
        !           330:                queue_remove(&eligible_tasks, task, task_t, swapped_tasks);
        !           331:                task->swap_flags &= ~TASK_SW_ELIGIBLE;
        !           332:        }
        !           333:        task_swapout_unlock();
        !           334: 
        !           335:        /* set state to avoid races with task_swappable(FALSE) */
        !           336:        task->swap_state = TASK_SW_GOING_OUT;
        !           337:        task->swap_rss = pmap_resident_count(task->map->pmap);
        !           338:        task_swaprss_out += task->swap_rss;
        !           339:        task->swap_ast_waiting = task->thr_act_count;
        !           340: 
        !           341:        /*
        !           342:         * halt all threads in this task:
        !           343:         * We don't need the thread list lock for traversal.
        !           344:         */
        !           345:        list = &task->thr_acts;
        !           346:        thr_act = (thread_act_t) queue_first(list);
        !           347:        while (!queue_end(list, (queue_entry_t) thr_act)) {
        !           348:                boolean_t swappable;
        !           349:                thread_act_t ract;
        !           350: 
        !           351:                thread = act_lock_thread(thr_act);
        !           352:                s = splsched();
        !           353:                if (!thread)
        !           354:                        swappable = (thr_act->swap_state != TH_SW_UNSWAPPABLE);
        !           355:                else {
        !           356:                        thread_lock(thread);
        !           357:                        swappable = TRUE;
        !           358:                        for (ract = thread->top_act; ract; ract = ract->lower)
        !           359:                                if (ract->swap_state == TH_SW_UNSWAPPABLE) {
        !           360:                                        swappable = FALSE;
        !           361:                                        break;
        !           362:                                }
        !           363:                }
        !           364:                if (swappable)
        !           365:                        thread_ast_set(thr_act, AST_SWAPOUT);
        !           366:                if (thread)
        !           367:                        thread_unlock(thread);
        !           368:                splx(s);
        !           369:                assert((thr_act->ast & AST_TERMINATE) == 0);
        !           370:                act_unlock_thread(thr_act);
        !           371:                thr_act = (thread_act_t) queue_next(&thr_act->thr_acts);
        !           372:        }
        !           373: 
        !           374:        task->swap_stamp = sched_tick;
        !           375:        task->swap_nswap++;
        !           376:        assert((task->swap_flags&TASK_SW_WANT_IN) == 0);
        !           377:        /* put task on the queue of swapped out tasks */
        !           378:        task_swapper_lock();
        !           379: #if    TASK_SW_DEBUG
        !           380:        if (task_swap_debug && on_swapped_list(task)) {
        !           381:                printf("task 0x%X already on list\n", task);
        !           382:                Debugger("");
        !           383:        }
        !           384: #endif /* TASK_SW_DEBUG */
        !           385:        queue_enter(&swapped_tasks, task, task_t, swapped_tasks);
        !           386:        tasks_swapped_out++;
        !           387:        task_swapouts++;
        !           388:        task_swapper_unlock();
        !           389:        task_unlock(task);
        !           390: 
        !           391:        return(KERN_SUCCESS);
        !           392: }
        !           393: 
        !           394: #ifdef TASK_SW_STATS
        !           395: int    task_sw_race_in = 0;
        !           396: int    task_sw_race_coming_in = 0;
        !           397: int    task_sw_race_going_out = 0;
        !           398: int    task_sw_before_ast = 0;
        !           399: int    task_sw_before_swap = 0;
        !           400: int    task_sw_after_swap = 0;
        !           401: int    task_sw_race_in_won = 0;
        !           402: int    task_sw_unswappable = 0;
        !           403: int    task_sw_act_inactive = 0;
        !           404: #endif /* TASK_SW_STATS */
        !           405: 
        !           406: /*
        !           407:  *     thread_swapout_enqueue is called by thread_halt_self when it 
        !           408:  *     processes AST_SWAPOUT to enqueue threads to be swapped out.
        !           409:  *     It must be called at normal interrupt priority for the
        !           410:  *     sake of the task_swapper_lock.
        !           411:  *
        !           412:  *     There can be races with task swapin here.
        !           413:  *     First lock task and decrement swap_ast_waiting count, and if
        !           414:  *     it's 0, we can decrement the residence count on the task's map
        !           415:  *     and set the task's swap state to TASK_SW_OUT.
        !           416:  */
        !           417: void
        !           418: thread_swapout_enqueue(thread_act_t thr_act)
        !           419: {
        !           420:        task_t task = thr_act->task;
        !           421:        task_lock(task);
        !           422:        /*
        !           423:         * If the swap_state is not TASK_SW_GOING_OUT, then
        !           424:         * task_swapin has beaten us to this operation, and
        !           425:         * we have nothing to do.
        !           426:         */
        !           427:        if (task->swap_state != TASK_SW_GOING_OUT) {
        !           428:                task_unlock(task);
        !           429:                return;
        !           430:        }
        !           431:        if (--task->swap_ast_waiting == 0) {
        !           432:                vm_map_t map = task->map;
        !           433:                task->swap_state = TASK_SW_OUT;
        !           434:                task_unlock(task);
        !           435:                mutex_lock(&map->s_lock);
        !           436:                vm_map_res_deallocate(map);
        !           437:                mutex_unlock(&map->s_lock);
        !           438:        } else
        !           439:                task_unlock(task);
        !           440: 
        !           441:        task_swapper_lock();
        !           442:        act_lock(thr_act);
        !           443:        if (! (thr_act->swap_state & TH_SW_TASK_SWAPPING)) {
        !           444:                /*
        !           445:                 * We lost a race with task_swapin(): don't enqueue.
        !           446:                 */
        !           447:        } else {
        !           448:                queue_enter(&swapout_thread_q, thr_act,
        !           449:                            thread_act_t, swap_queue);
        !           450:                thread_wakeup((event_t)&swapout_thread_q);
        !           451:        }
        !           452:        act_unlock(thr_act);
        !           453:        task_swapper_unlock();
        !           454: }
        !           455: 
        !           456: /*
        !           457:  *     task_swap_swapout_thread: [exported]
        !           458:  *
        !           459:  *     Executes as a separate kernel thread.
        !           460:  *     Its job is to swap out threads that have been halted by AST_SWAPOUT.
        !           461:  */
        !           462: void
        !           463: task_swap_swapout_thread(void)
        !           464: {
        !           465:        thread_act_t thr_act;
        !           466:        thread_t thread, nthread;
        !           467:        task_t task;
        !           468:        int s;
        !           469: 
        !           470:        thread_swappable(current_act(), FALSE);
        !           471:        stack_privilege(current_thread());
        !           472: 
        !           473:        spllo();
        !           474: 
        !           475:        while (TRUE) {
        !           476:                task_swapper_lock();
        !           477:                while (! queue_empty(&swapout_thread_q)) {
        !           478: 
        !           479:                        queue_remove_first(&swapout_thread_q, thr_act,
        !           480:                                           thread_act_t, swap_queue);
        !           481:                        /*
        !           482:                         * If we're racing with task_swapin, we need
        !           483:                         * to make it safe for it to do remque on the
        !           484:                         * thread, so make its links point to itself.
        !           485:                         * Allowing this ugliness is cheaper than 
        !           486:                         * making task_swapin search the entire queue.
        !           487:                         */
        !           488:                        act_lock(thr_act);
        !           489:                        queue_init((queue_t) &thr_act->swap_queue);
        !           490:                        act_unlock(thr_act);
        !           491:                        task_swapper_unlock();
        !           492:                        /*
        !           493:                         * Wait for thread's RUN bit to be deasserted.
        !           494:                         */
        !           495:                        thread = act_lock_thread(thr_act);
        !           496:                        if (thread == THREAD_NULL)
        !           497:                                act_unlock_thread(thr_act);
        !           498:                        else {
        !           499:                                boolean_t r;
        !           500: 
        !           501:                                thread_reference(thread);
        !           502:                                thread_hold(thr_act);
        !           503:                                act_unlock_thread(thr_act);
        !           504:                                r = thread_stop_wait(thread);
        !           505:                                nthread = act_lock_thread(thr_act);
        !           506:                                thread_release(thr_act);
        !           507:                                thread_deallocate(thread);
        !           508:                                act_unlock_thread(thr_act);
        !           509:                                if (!r || nthread != thread) {
        !           510:                                        task_swapper_lock();
        !           511:                                        continue;
        !           512:                                }
        !           513:                        }
        !           514:                        task = thr_act->task;
        !           515:                        task_lock(task);
        !           516:                        /* 
        !           517:                         * we can race with swapin, which would set the
        !           518:                         * state to TASK_SW_IN. 
        !           519:                         */
        !           520:                        if ((task->swap_state != TASK_SW_OUT) &&
        !           521:                            (task->swap_state != TASK_SW_GOING_OUT)) {
        !           522:                                task_unlock(task);
        !           523:                                task_swapper_lock();
        !           524:                                TASK_STATS_INCR(task_sw_race_in_won);
        !           525:                                if (thread != THREAD_NULL)
        !           526:                                        thread_unstop(thread);
        !           527:                                continue;
        !           528:                        }
        !           529:                        nthread = act_lock_thread(thr_act);
        !           530:                        if (nthread != thread || thr_act->active == FALSE) {
        !           531:                                act_unlock_thread(thr_act);
        !           532:                                task_unlock(task);
        !           533:                                task_swapper_lock();
        !           534:                                TASK_STATS_INCR(task_sw_act_inactive);
        !           535:                                if (thread != THREAD_NULL)
        !           536:                                        thread_unstop(thread);
        !           537:                                continue;
        !           538:                        }
        !           539:                        s = splsched();
        !           540:                        if (thread != THREAD_NULL)
        !           541:                                thread_lock(thread);
        !           542:                        /* 
        !           543:                         * Thread cannot have been swapped out yet because
        !           544:                         * TH_SW_TASK_SWAPPING was set in AST.  If task_swapin
        !           545:                         * beat us here, we either wouldn't have found it on
        !           546:                         * the queue, or the task->swap_state would have
        !           547:                         * changed.  The synchronization is on the
        !           548:                         * task's swap_state and the task_lock.
        !           549:                         * The thread can't be swapped in any other way
        !           550:                         * because its task has been swapped.
        !           551:                         */
        !           552:                        assert(thr_act->swap_state & TH_SW_TASK_SWAPPING);
        !           553:                        assert(thread == THREAD_NULL ||
        !           554:                               !(thread->state & (TH_SWAPPED_OUT|TH_RUN)));
        !           555:                        assert((thr_act->swap_state & TH_SW_STATE) == TH_SW_IN);
        !           556:                        /* assert(thread->state & TH_HALTED); */
        !           557:                        /* this also clears TH_SW_TASK_SWAPPING flag */
        !           558:                        thr_act->swap_state = TH_SW_GOING_OUT;
        !           559:                        if (thread != THREAD_NULL) {
        !           560:                                if (thread->top_act == thr_act) {
        !           561:                                        thread->state |= TH_SWAPPED_OUT;
        !           562:                                        /*
        !           563:                                         * Once we unlock the task, things can happen
        !           564:                                         * to the thread, so make sure it's consistent
        !           565:                                         * for thread_swapout.
        !           566:                                         */
        !           567:                                }
        !           568:                                thread->ref_count++;
        !           569:                                thread_unlock(thread);
        !           570:                                thread_unstop(thread);
        !           571:                        }
        !           572:                        splx(s);
        !           573:                        act_locked_act_reference(thr_act);
        !           574:                        act_unlock_thread(thr_act);
        !           575:                        task_unlock(task);
        !           576: 
        !           577:                        thread_swapout(thr_act);        /* do the work */
        !           578: 
        !           579:                        if (thread != THREAD_NULL)
        !           580:                                thread_deallocate(thread);
        !           581:                        act_deallocate(thr_act);
        !           582:                        task_swapper_lock();
        !           583:                }
        !           584:                assert_wait((event_t)&swapout_thread_q, THREAD_UNINT);
        !           585:                task_swapper_unlock();
        !           586:                thread_block((void (*)(void)) 0);
        !           587:        }
        !           588: }
        !           589: 
        !           590: /*
        !           591:  *     task_swapin:
        !           592:  *
        !           593:  *     Make a task resident.
        !           594:  *     Performs all of the work to make a task resident and possibly
        !           595:  *     non-swappable.  If we race with a competing task_swapin call,
        !           596:  *     we wait for its completion, then return.
        !           597:  *
        !           598:  *     Locking: no locks held upon entry and exit.
        !           599:  *
        !           600:  *     Note that TASK_SW_MAKE_UNSWAPPABLE can only be set when the
        !           601:  *     state is TASK_SW_COMING_IN.
        !           602:  */
        !           603: 
        !           604: kern_return_t
        !           605: task_swapin(task_t task, boolean_t make_unswappable)
        !           606: {
        !           607:        register queue_head_t   *list;
        !           608:        register thread_act_t   thr_act, next;
        !           609:        thread_t                thread;
        !           610:        int                     s;
        !           611:        boolean_t               swappable = TRUE;
        !           612: 
        !           613:        task_lock(task);
        !           614:        switch (task->swap_state) {
        !           615:            case TASK_SW_OUT:
        !           616:                        {
        !           617:                        vm_map_t map = task->map;
        !           618:                        /*
        !           619:                         * Task has made it all the way out, which means
        !           620:                         * that vm_map_res_deallocate has been done; set 
        !           621:                         * state to TASK_SW_COMING_IN, then bring map
        !           622:                         * back in.  We could actually be racing with
        !           623:                         * the thread_swapout_enqueue, which does the
        !           624:                         * vm_map_res_deallocate, but that race is covered.
        !           625:                         */
        !           626:                        task->swap_state = TASK_SW_COMING_IN;
        !           627:                        assert(task->swap_ast_waiting == 0);
        !           628:                        assert(map->res_count >= 0);
        !           629:                        task_unlock(task);
        !           630:                        mutex_lock(&map->s_lock);
        !           631:                        vm_map_res_reference(map);
        !           632:                        mutex_unlock(&map->s_lock);
        !           633:                        task_lock(task);
        !           634:                        assert(task->swap_state == TASK_SW_COMING_IN);
        !           635:                        }
        !           636:                        break;
        !           637: 
        !           638:            case TASK_SW_GOING_OUT:
        !           639:                        /*
        !           640:                         * Task isn't all the way out yet.  There is
        !           641:                         * still at least one thread not swapped, and
        !           642:                         * vm_map_res_deallocate has not been done.
        !           643:                         */
        !           644:                        task->swap_state = TASK_SW_COMING_IN;
        !           645:                        assert(task->swap_ast_waiting > 0 ||
        !           646:                               (task->swap_ast_waiting == 0 &&
        !           647:                                task->thr_act_count == 0));
        !           648:                        assert(task->map->res_count > 0);
        !           649:                        TASK_STATS_INCR(task_sw_race_going_out);
        !           650:                        break;
        !           651:            case TASK_SW_IN:
        !           652:                        assert(task->map->res_count > 0);
        !           653: #if    TASK_SW_DEBUG
        !           654:                        task_swapper_lock();
        !           655:                        if (task_swap_debug && on_swapped_list(task)) {
        !           656:                                printf("task 0x%X on list, state is SW_IN\n",
        !           657:                                        task);
        !           658:                                Debugger("");
        !           659:                        }
        !           660:                        task_swapper_unlock();
        !           661: #endif /* TASK_SW_DEBUG */
        !           662:                        TASK_STATS_INCR(task_sw_race_in);
        !           663:                        if (make_unswappable) {
        !           664:                                task->swap_state = TASK_SW_UNSWAPPABLE;
        !           665:                                task_unlock(task);
        !           666:                                task_swapout_ineligible(task);
        !           667:                        } else
        !           668:                                task_unlock(task);
        !           669:                        return(KERN_SUCCESS);
        !           670:            case TASK_SW_COMING_IN:
        !           671:                        /* 
        !           672:                         * Raced with another task_swapin and lost;
        !           673:                         * wait for other one to complete first
        !           674:                         */
        !           675:                        assert(task->map->res_count >= 0);
        !           676:                        /*
        !           677:                         * set MAKE_UNSWAPPABLE so that whoever is swapping
        !           678:                         * the task in will make it unswappable, and return
        !           679:                         */
        !           680:                        if (make_unswappable)
        !           681:                                task->swap_flags |= TASK_SW_MAKE_UNSWAPPABLE;
        !           682:                        task->swap_flags |= TASK_SW_WANT_IN;
        !           683:                        assert_wait((event_t)&task->swap_state, THREAD_UNINT);
        !           684:                        task_unlock(task);
        !           685:                        thread_block((void (*)(void)) 0);
        !           686:                        TASK_STATS_INCR(task_sw_race_coming_in);
        !           687:                        return(KERN_SUCCESS);
        !           688:            case TASK_SW_UNSWAPPABLE:
        !           689:                        /* 
        !           690:                         * This can happen, since task_terminate 
        !           691:                         * unconditionally calls task_swapin.
        !           692:                         */
        !           693:                        task_unlock(task);
        !           694:                        return(KERN_SUCCESS);
        !           695:            default:
        !           696:                        panic("task_swapin bad state");
        !           697:                        break;
        !           698:        }
        !           699:        if (make_unswappable)
        !           700:                task->swap_flags |= TASK_SW_MAKE_UNSWAPPABLE;
        !           701:        assert(task->swap_state == TASK_SW_COMING_IN);
        !           702:        task_swapper_lock();
        !           703: #if    TASK_SW_DEBUG
        !           704:        if (task_swap_debug && !on_swapped_list(task)) {
        !           705:                printf("task 0x%X not on list\n", task);
        !           706:                Debugger("");
        !           707:        }
        !           708: #endif /* TASK_SW_DEBUG */
        !           709:        queue_remove(&swapped_tasks, task, task_t, swapped_tasks);
        !           710:        tasks_swapped_out--;
        !           711:        task_swapins++;
        !           712:        task_swapper_unlock();
        !           713: 
        !           714:        /*
        !           715:         * Iterate through all threads for this task and 
        !           716:         * release them, as required.  They may not have been swapped
        !           717:         * out yet.  The task remains locked throughout.
        !           718:         */
        !           719:        list = &task->thr_acts;
        !           720:        thr_act = (thread_act_t) queue_first(list);
        !           721:        while (!queue_end(list, (queue_entry_t) thr_act)) {
        !           722:                boolean_t need_to_release;
        !           723:                next = (thread_act_t) queue_next(&thr_act->thr_acts);
        !           724:                /*
        !           725:                 * Keep task_swapper_lock across thread handling
        !           726:                 * to synchronize with task_swap_swapout_thread
        !           727:                 */
        !           728:                task_swapper_lock();
        !           729:                thread = act_lock_thread(thr_act);
        !           730:                s = splsched();
        !           731:                if (thr_act->ast & AST_SWAPOUT) {
        !           732:                        /* thread hasn't gotten the AST yet, just clear it */
        !           733:                        thread_ast_clear(thr_act, AST_SWAPOUT);
        !           734:                        need_to_release = FALSE;
        !           735:                        TASK_STATS_INCR(task_sw_before_ast);
        !           736:                        splx(s);
        !           737:                        act_unlock_thread(thr_act);
        !           738:                } else {
        !           739:                        /*
        !           740:                         * If AST_SWAPOUT was cleared, then thread_hold,
        !           741:                         * or equivalent was done.
        !           742:                         */
        !           743:                        need_to_release = TRUE;
        !           744:                        /*
        !           745:                         * Thread has hit AST, but it may not have
        !           746:                         * been dequeued yet, so we need to check.
        !           747:                         * NOTE: the thread may have been dequeued, but
        !           748:                         * has not yet been swapped (the task_swapper_lock
        !           749:                         * has been dropped, but the thread is not yet
        !           750:                         * locked), and the TH_SW_TASK_SWAPPING flag may 
        !           751:                         * not have been cleared.  In this case, we will do 
        !           752:                         * an extra remque, which the task_swap_swapout_thread
        !           753:                         * has made safe, and clear the flag, which is also
        !           754:                         * checked by the t_s_s_t before doing the swapout.
        !           755:                         */
        !           756:                        if (thread)
        !           757:                                thread_lock(thread);
        !           758:                        if (thr_act->swap_state & TH_SW_TASK_SWAPPING) {
        !           759:                                /* 
        !           760:                                 * hasn't yet been dequeued for swapout,
        !           761:                                 * so clear flags and dequeue it first.
        !           762:                                 */
        !           763:                                thr_act->swap_state &= ~TH_SW_TASK_SWAPPING;
        !           764:                                assert(thr_act->thread == THREAD_NULL || 
        !           765:                                       !(thr_act->thread->state &
        !           766:                                         TH_SWAPPED_OUT));
        !           767:                                queue_remove(&swapout_thread_q, thr_act,
        !           768:                                             thread_act_t, swap_queue);
        !           769:                                TASK_STATS_INCR(task_sw_before_swap);
        !           770:                        } else {
        !           771:                                TASK_STATS_INCR(task_sw_after_swap);
        !           772:                                /*
        !           773:                                 * It's possible that the thread was
        !           774:                                 * made unswappable before hitting the
        !           775:                                 * AST, in which case it's still running.
        !           776:                                 */
        !           777:                                if (thr_act->swap_state == TH_SW_UNSWAPPABLE) {
        !           778:                                        need_to_release = FALSE;
        !           779:                                        TASK_STATS_INCR(task_sw_unswappable);
        !           780:                                }
        !           781:                        }
        !           782:                        if (thread)
        !           783:                                thread_unlock(thread);
        !           784:                        splx(s);
        !           785:                        act_unlock_thread(thr_act);
        !           786:                }
        !           787:                task_swapper_unlock();
        !           788: 
        !           789:                /* 
        !           790:                 * thread_release will swap in the thread if it's been
        !           791:                 * swapped out.
        !           792:                 */
        !           793:                if (need_to_release) {
        !           794:                        act_lock_thread(thr_act);
        !           795:                        thread_release(thr_act);
        !           796:                        act_unlock_thread(thr_act);
        !           797:                }
        !           798:                thr_act = next;
        !           799:        }
        !           800: 
        !           801:        if (task->swap_flags & TASK_SW_MAKE_UNSWAPPABLE) {
        !           802:                task->swap_flags &= ~TASK_SW_MAKE_UNSWAPPABLE;
        !           803:                task->swap_state = TASK_SW_UNSWAPPABLE;
        !           804:                swappable = FALSE;
        !           805:        } else {
        !           806:                task->swap_state = TASK_SW_IN;
        !           807:        }
        !           808: 
        !           809:        task_swaprss_in += pmap_resident_count(task->map->pmap);
        !           810:        task_swap_total_time += sched_tick - task->swap_stamp;
        !           811:        /* note when task came back in */
        !           812:        task->swap_stamp = sched_tick;
        !           813:        if (task->swap_flags & TASK_SW_WANT_IN) {
        !           814:                task->swap_flags &= ~TASK_SW_WANT_IN;
        !           815:                thread_wakeup((event_t)&task->swap_state);
        !           816:        }
        !           817:        assert((task->swap_flags & TASK_SW_ELIGIBLE) == 0);
        !           818:        task_unlock(task);
        !           819: #if    TASK_SW_DEBUG
        !           820:        task_swapper_lock();
        !           821:        if (task_swap_debug && on_swapped_list(task)) {
        !           822:                printf("task 0x%X on list at end of swap in\n", task);
        !           823:                Debugger("");
        !           824:        }
        !           825:        task_swapper_unlock();
        !           826: #endif /* TASK_SW_DEBUG */
        !           827:        /*
        !           828:         * Make the task eligible to be swapped again
        !           829:         */
        !           830:        if (swappable)
        !           831:                task_swapout_eligible(task);
        !           832:        return(KERN_SUCCESS);
        !           833: }
        !           834: 
        !           835: void wake_task_swapper(boolean_t now); /* forward */
        !           836: 
        !           837: /*
        !           838:  *     wake_task_swapper: [exported]
        !           839:  *
        !           840:  *     Wakes up task swapper if now == TRUE or if at least
        !           841:  *     task_swap_cycle_time has elapsed since the last call.
        !           842:  *
        !           843:  *     NOTE: this function is not multithreaded, so if there is
        !           844:  *     more than one caller, it must be modified.
        !           845:  */
        !           846: void
        !           847: wake_task_swapper(boolean_t now)
        !           848: {
        !           849:        /* last_task_swap_cycle may require locking */
        !           850:        if (now ||
        !           851:            (sched_tick > (last_task_swap_cycle + task_swap_cycle_time))) {
        !           852:                last_task_swap_cycle = sched_tick;
        !           853:                if (task_swap_debug)
        !           854:                        printf("wake_task_swapper: waking swapper\n");
        !           855:                thread_wakeup((event_t)&swapped_tasks); /* poke swapper */
        !           856:        }
        !           857: }
        !           858: 
        !           859: task_t pick_intask(void);      /* forward */
        !           860: /*
        !           861:  * pick_intask:
        !           862:  * returns a task to be swapped in, or TASK_NULL if nothing suitable is found.
        !           863:  *
        !           864:  * current algorithm: Return the task that has been swapped out the 
        !           865:  *     longest, as long as it is > min_swap_time.  It will be dequeued
        !           866:  *     if actually swapped in.
        !           867:  *
        !           868:  * NOTE:**********************************************
        !           869:  * task->swap_rss (the size when the task was swapped out) could be used to
        !           870:  * further refine the selection.  Another possibility would be to look at
        !           871:  * the state of the thread(s) to see if the task/threads would run if they
        !           872:  * were swapped in.
        !           873:  * ***************************************************
        !           874:  *
        !           875:  * Locking:  no locks held upon entry and exit.
        !           876:  */
        !           877: task_t
        !           878: pick_intask(void)
        !           879: {
        !           880:        register task_t         task = TASK_NULL;
        !           881: 
        !           882:        task_swapper_lock();
        !           883:        /* the oldest task is the first one */
        !           884:        if (!queue_empty(&swapped_tasks)) {
        !           885:                task = (task_t) queue_first(&swapped_tasks);
        !           886:                assert(task != TASK_NULL);
        !           887:                /* Make sure it's been out min_swap_time */
        !           888:                if ((sched_tick - task->swap_stamp) < min_swap_time)
        !           889:                        task = TASK_NULL;
        !           890:        }
        !           891:        task_swapper_unlock();
        !           892:        return(task);
        !           893: #if    0
        !           894:        /*
        !           895:         * This code looks at the entire list of swapped tasks, but since
        !           896:         * it does not yet do anything but look at time swapped, we 
        !           897:         * can simply use the fact that the queue is ordered, and take 
        !           898:         * the first one off the queue.
        !           899:         */
        !           900:        task = (task_t)queue_first(&swapped_tasks);
        !           901:        while (!queue_end(&swapped_tasks, (queue_entry_t)task)) {
        !           902:                task_lock(task);
        !           903:                tmp_time = sched_tick - task->swap_stamp;
        !           904:                if (tmp_time > min_swap_time && tmp_time > time_swapped) {
        !           905:                        target_task = task;
        !           906:                        time_swapped = tmp_time;
        !           907:                }
        !           908:                task_unlock(task);
        !           909:                task = (task_t)queue_next(&task->swapped_tasks);
        !           910:        }
        !           911:        task_swapper_unlock();
        !           912:        return(target_task);
        !           913: #endif
        !           914: }
        !           915: 
        !           916: task_t pick_outtask(void);     /* forward */
        !           917: /*
        !           918:  * pick_outtask:
        !           919:  * returns a task to be swapped out, with a reference on the task,
        !           920:  * or NULL if no suitable task is found.
        !           921:  *
        !           922:  * current algorithm:
        !           923:  * 
        !           924:  * Examine all eligible tasks.  While looking, use the first thread in 
        !           925:  * each task as an indication of the task's activity.  Count up 
        !           926:  * "active" threads (those either runnable or sleeping).  If the task 
        !           927:  * is active (by these criteria), swapped in, and resident 
        !           928:  * for at least min_res_time, then select the task with the largest 
        !           929:  * number of pages in memory.  If there are less 
        !           930:  * than min_active_tasks active tasks in the system, then don't 
        !           931:  * swap anything out (this avoids swapping out the only running task 
        !           932:  * in the system, for example).
        !           933:  *
        !           934:  * NOTE:  the task selected will not be removed from the eligible list.
        !           935:  *       This means that it will be selected again if it is not swapped
        !           936:  *       out, where it is removed from the list.
        !           937:  *
        !           938:  * Locking: no locks held upon entry and exit.  Task_swapout_lock must be
        !           939:  *         taken before task locks.
        !           940:  *
        !           941:  * ***************************************************
        !           942:  * TBD:
        !           943:  * This algorithm only examines the first thread in the task.  Currently, since
        !           944:  * most swappable tasks in the system are single-threaded, this generalization
        !           945:  * works reasonably well.  However, the algorithm should be changed
        !           946:  * to consider all threads in the task if more multi-threaded tasks were used.  
        !           947:  * ***************************************************
        !           948:  */
        !           949: 
        !           950: #ifdef TASK_SW_STATS
        !           951: int inactive_task_count = 0;
        !           952: int empty_task_count = 0;
        !           953: #endif /* TASK_SW_STATS */
        !           954: 
        !           955: task_t
        !           956: pick_outtask(void)
        !           957: {
        !           958:        register task_t         task;
        !           959:        register task_t         target_task = TASK_NULL;
        !           960:        unsigned long           task_rss;
        !           961:        unsigned long           target_rss = 0;
        !           962:        boolean_t               wired;
        !           963:        boolean_t               active;
        !           964:        int                     nactive = 0;
        !           965: 
        !           966:        task_swapout_lock();
        !           967:        if (queue_empty(&eligible_tasks)) {
        !           968:                /* not likely to happen */
        !           969:                task_swapout_unlock();
        !           970:                return(TASK_NULL);
        !           971:        }
        !           972:        task = (task_t)queue_first(&eligible_tasks);
        !           973:        while (!queue_end(&eligible_tasks, (queue_entry_t)task)) {
        !           974:                int s;
        !           975:                register thread_act_t thr_act;
        !           976:                thread_t th;
        !           977:                
        !           978: 
        !           979:                task_lock(task);
        !           980:                /*
        !           981:                 * Don't swap real-time tasks.
        !           982:                 * XXX Should we enforce that or can we let really critical
        !           983:                 * tasks use task_swappable() to make sure they never end up
        !           984:                 * n the eligible list ?
        !           985:                 */
        !           986:                if (task->policy & POLICYCLASS_FIXEDPRI) {
        !           987:                        goto tryagain;
        !           988:                }
        !           989:                if (!task->active) {
        !           990:                        TASK_STATS_INCR(inactive_task_count);
        !           991:                        goto tryagain;
        !           992:                }
        !           993:                if (task->res_act_count == 0) {
        !           994:                        TASK_STATS_INCR(empty_task_count);
        !           995:                        goto tryagain;
        !           996:                }
        !           997:                assert(!queue_empty(&task->thr_acts));
        !           998:                thr_act = (thread_act_t)queue_first(&task->thr_acts);
        !           999:                active = FALSE;
        !          1000:                th = act_lock_thread(thr_act);
        !          1001:                s = splsched();
        !          1002:                if (th != THREAD_NULL)
        !          1003:                        thread_lock(th);
        !          1004:                if ((th == THREAD_NULL) ||
        !          1005:                    (th->state == TH_RUN) ||
        !          1006:                    (th->state & TH_WAIT)) {
        !          1007:                        /*
        !          1008:                         * thread is "active": either runnable 
        !          1009:                         * or sleeping.  Count it and examine 
        !          1010:                         * it further below.
        !          1011:                         */
        !          1012:                        nactive++;
        !          1013:                        active = TRUE;
        !          1014:                }
        !          1015:                if (th != THREAD_NULL)
        !          1016:                        thread_unlock(th);
        !          1017:                splx(s);
        !          1018:                act_unlock_thread(thr_act);
        !          1019:                if (active &&
        !          1020:                    (task->swap_state == TASK_SW_IN) &&
        !          1021:                    ((sched_tick - task->swap_stamp) > min_res_time)) {
        !          1022:                        long rescount = pmap_resident_count(task->map->pmap);
        !          1023:                        /*
        !          1024:                         * thread must be "active", task must be swapped
        !          1025:                         * in and resident for at least min_res_time
        !          1026:                         */
        !          1027: #if 0
        !          1028: /* DEBUG Test round-robin strategy.  Picking biggest task could cause extreme
        !          1029:  * unfairness to such large interactive programs as xterm.  Instead, pick the
        !          1030:  * first task that has any pages resident:
        !          1031:  */
        !          1032:                        if (rescount > 1) {
        !          1033:                                task->ref_count++;
        !          1034:                                target_task = task;
        !          1035:                                task_unlock(task);
        !          1036:                                task_swapout_unlock();
        !          1037:                                return(target_task);
        !          1038:                        }
        !          1039: #else
        !          1040:                        if (rescount > target_rss) {
        !          1041:                                /*
        !          1042:                                 * task is not swapped, and it has the
        !          1043:                                 * largest rss seen so far.
        !          1044:                                 */
        !          1045:                                task->ref_count++;
        !          1046:                                target_rss = rescount;
        !          1047:                                assert(target_task != task);
        !          1048:                                if (target_task != TASK_NULL)
        !          1049:                                        task_deallocate(target_task);
        !          1050:                                target_task = task;
        !          1051:                        }
        !          1052: #endif
        !          1053:                }
        !          1054: tryagain:
        !          1055:                task_unlock(task);
        !          1056:                task = (task_t)queue_next(&task->swapped_tasks);
        !          1057:        }
        !          1058:        task_swapout_unlock();
        !          1059:        /* only swap out if there are at least min_active_tasks */
        !          1060:        if (nactive < min_active_tasks) {
        !          1061:                if (target_task != TASK_NULL) {
        !          1062:                        task_deallocate(target_task);
        !          1063:                        target_task = TASK_NULL;
        !          1064:                }
        !          1065:        }
        !          1066:        return(target_task);
        !          1067: }
        !          1068: 
        !          1069: #if    TASK_SW_DEBUG
        !          1070: void print_pid(task_t task, unsigned long n1, unsigned long n2,
        !          1071:               const char *comp, const char *inout);    /* forward */
        !          1072: void
        !          1073: print_pid(
        !          1074:        task_t task,
        !          1075:        unsigned long n1,
        !          1076:        unsigned long n2,
        !          1077:        const char *comp,
        !          1078:        const char *inout)
        !          1079: {
        !          1080:        long rescount;
        !          1081:        task_lock(task);
        !          1082:        rescount = pmap_resident_count(task->map->pmap);
        !          1083:        task_unlock(task);
        !          1084:        printf("task_swapper: swapped %s task %x; %d %s %d; res=%d\n",
        !          1085:                inout, task, n1, comp, n2, rescount);
        !          1086: }
        !          1087: #endif
        !          1088: 
        !          1089: /*
        !          1090:  *     task_swapper: [exported]
        !          1091:  *
        !          1092:  *     Executes as a separate kernel thread.
        !          1093:  */
        !          1094: #define MAX_LOOP 3
        !          1095: void
        !          1096: task_swapper(void)
        !          1097: {
        !          1098:        task_t  outtask, intask;
        !          1099:        int timeout;
        !          1100:        int loopcnt = 0;
        !          1101:        boolean_t start_swapping;
        !          1102:        boolean_t stop_swapping;
        !          1103:        int local_page_free_avg;
        !          1104:        extern int hz;
        !          1105: 
        !          1106:        thread_swappable(current_act(), FALSE);
        !          1107:        stack_privilege(current_thread());
        !          1108: 
        !          1109:        spllo();
        !          1110: 
        !          1111:        for (;;) {
        !          1112:        local_page_free_avg = vm_page_free_avg;
        !          1113:        while (TRUE) {
        !          1114: #if    0
        !          1115:                if (task_swap_debug)
        !          1116:                        printf("task_swapper: top of loop; cnt = %d\n",loopcnt);
        !          1117: #endif
        !          1118:                intask = pick_intask();
        !          1119: 
        !          1120:                start_swapping = ((vm_pageout_rate_avg > swap_start_pageout_rate) ||
        !          1121:                                  (vm_grab_rate_avg > max_grab_rate));
        !          1122:                stop_swapping = (vm_pageout_rate_avg < swap_stop_pageout_rate);
        !          1123: 
        !          1124:                /*
        !          1125:                 * If a lot of paging is going on, or another task should come
        !          1126:                 * in but memory is tight, find something to swap out and start
        !          1127:                 * it.  Don't swap any task out if task swapping is disabled.
        !          1128:                 * vm_page_queue_free_lock protects the vm globals.
        !          1129:                 */
        !          1130:                outtask = TASK_NULL;
        !          1131:                if (start_swapping ||
        !          1132:                    (!stop_swapping && intask &&
        !          1133:                     ((local_page_free_avg / AVE_SCALE) < vm_page_free_target))
        !          1134:                   ) {
        !          1135:                        if (task_swap_enable &&
        !          1136:                            (outtask = pick_outtask()) &&
        !          1137:                            (task_swapout(outtask) == KERN_SUCCESS)) {
        !          1138:                                unsigned long rss;
        !          1139: #if    TASK_SW_DEBUG
        !          1140:                                if (task_swap_debug)
        !          1141:                                    print_pid(outtask, local_page_free_avg / AVE_SCALE,
        !          1142:                                              vm_page_free_target, "<",
        !          1143:                                              "out");
        !          1144: #endif
        !          1145:                                rss = outtask->swap_rss;
        !          1146:                                if (outtask->swap_nswap == 1)
        !          1147:                                        rss /= 2; /* divide by 2 if never out */
        !          1148:                                local_page_free_avg += (rss/short_avg_interval) * AVE_SCALE;
        !          1149:                        }
        !          1150:                        if (outtask != TASK_NULL)
        !          1151:                                task_deallocate(outtask);
        !          1152:                }
        !          1153: 
        !          1154:                /*
        !          1155:                 * If there is an eligible task to bring in and there are at
        !          1156:                 * least vm_page_free_target free pages, swap it in.  If task
        !          1157:                 * swapping has been disabled, bring the task in anyway.
        !          1158:                 */
        !          1159:                if (intask && ((local_page_free_avg / AVE_SCALE) >=
        !          1160:                                                        vm_page_free_target ||
        !          1161:                                stop_swapping || !task_swap_enable)) {
        !          1162:                        if (task_swapin(intask, FALSE) == KERN_SUCCESS) {
        !          1163:                                unsigned long rss;
        !          1164: #if    TASK_SW_DEBUG
        !          1165:                                if (task_swap_debug)
        !          1166:                                    print_pid(intask, local_page_free_avg / AVE_SCALE,
        !          1167:                                              vm_page_free_target, ">=",
        !          1168:                                              "in");
        !          1169: #endif
        !          1170:                                rss = intask->swap_rss;
        !          1171:                                if (intask->swap_nswap == 1)
        !          1172:                                        rss /= 2; /* divide by 2 if never out */
        !          1173:                                local_page_free_avg -= (rss/short_avg_interval) * AVE_SCALE;
        !          1174:                        }
        !          1175:                }
        !          1176:                /*
        !          1177:                 * XXX
        !          1178:                 * Here we have to decide whether to continue swapping
        !          1179:                 * in and/or out before sleeping.  The decision should
        !          1180:                 * be made based on the previous action (swapin/out) and
        !          1181:                 * current system parameters, such as paging rates and
        !          1182:                 * demand.
        !          1183:                 * The function, compute_vm_averages, which does these
        !          1184:                 * calculations, depends on being called every second,
        !          1185:                 * so we can't just do the same thing.
        !          1186:                 */
        !          1187:                if (++loopcnt < MAX_LOOP)
        !          1188:                        continue;
        !          1189: 
        !          1190:                /*
        !          1191:                 * Arrange to be awakened if paging is still heavy or there are
        !          1192:                 * any tasks partially or completely swapped out.  (Otherwise,
        !          1193:                 * the wakeup will come from the external trigger(s).)
        !          1194:                 */
        !          1195:                timeout = 0;
        !          1196:                if (start_swapping)
        !          1197:                        timeout = task_swap_cycle_time;
        !          1198:                else {
        !          1199:                        task_swapper_lock();
        !          1200:                        if (!queue_empty(&swapped_tasks))
        !          1201:                                timeout = min_swap_time;
        !          1202:                        task_swapper_unlock();
        !          1203:                }
        !          1204:                assert_wait((event_t)&swapped_tasks, THREAD_UNINT);
        !          1205:                if (timeout) {
        !          1206:                        if (task_swap_debug)
        !          1207:                                printf("task_swapper: set timeout of %d\n",
        !          1208:                                                                timeout);
        !          1209:                        thread_set_timeout(timeout, NSEC_PER_SEC);
        !          1210:                }
        !          1211:                if (task_swap_debug)
        !          1212:                        printf("task_swapper: blocking\n");
        !          1213:                thread_block((void (*)(void)) 0);
        !          1214:                if (timeout) {
        !          1215:                        thread_cancel_timeout(current_thread());
        !          1216:                }
        !          1217:                /* reset locals */
        !          1218:                loopcnt = 0;
        !          1219:                local_page_free_avg = vm_page_free_avg;
        !          1220:        }
        !          1221:        }
        !          1222: }
        !          1223: 
        !          1224: /* from BSD */
        !          1225: #define ave(smooth, cnt, time) \
        !          1226:        smooth = ((time - 1) * (smooth) + ((cnt) * AVE_SCALE)) / (time)
        !          1227: 
        !          1228: /*
        !          1229:  * We estimate the system paging load in more than one metric: 
        !          1230:  *     1) the total number of calls into the function, vm_page_grab, 
        !          1231:  *        which allocates all page frames for real pages.
        !          1232:  *     2) the total number of pages paged in and out of paging files.
        !          1233:  *        This is a measure of page cleaning and faulting from backing
        !          1234:  *        store.
        !          1235:  *
        !          1236:  * When either metric passes a threshold, tasks are swapped out.
        !          1237:  */
        !          1238: long last_grab_count = 0;
        !          1239: long last_pageout_count = 0;
        !          1240: 
        !          1241: /*
        !          1242:  * compute_vm_averages: [exported]
        !          1243:  *
        !          1244:  * This function is to be called once a second to calculate average paging
        !          1245:  * demand and average numbers of free pages for use by the task swapper.
        !          1246:  * Can also be used to wake up task swapper at desired thresholds.
        !          1247:  *
        !          1248:  * NOTE: this function is single-threaded, and requires locking if
        !          1249:  *     ever there are multiple callers.
        !          1250:  */
        !          1251: void
        !          1252: compute_vm_averages(void)
        !          1253: {
        !          1254:        extern unsigned long vm_page_grab_count;
        !          1255:        long grab_count, pageout_count;
        !          1256:        int i;
        !          1257: 
        !          1258:        ave(vm_page_free_avg, vm_page_free_count, short_avg_interval);
        !          1259:        ave(vm_page_free_longavg, vm_page_free_count, long_avg_interval);
        !          1260: 
        !          1261:        /* 
        !          1262:         * NOTE: the vm_page_grab_count and vm_stat structure are 
        !          1263:         * under control of vm_page_queue_free_lock.  We're simply reading
        !          1264:         * memory here, and the numbers don't depend on each other, so
        !          1265:         * no lock is taken.
        !          1266:         */
        !          1267: 
        !          1268:        grab_count = vm_page_grab_count;
        !          1269:        pageout_count = 0;
        !          1270:        for (i = 0; i < NCPUS; i++) {
        !          1271:                pageout_count += vm_stat[i].pageouts;
        !          1272:        }
        !          1273: 
        !          1274:        ave(vm_pageout_rate_avg, pageout_count - last_pageout_count,
        !          1275:            short_avg_interval);
        !          1276:        ave(vm_pageout_rate_longavg, pageout_count - last_pageout_count,
        !          1277:            long_avg_interval);
        !          1278:        ave(vm_grab_rate_avg, grab_count - last_grab_count,
        !          1279:            short_avg_interval);
        !          1280:        last_grab_count = grab_count;
        !          1281:        last_pageout_count = pageout_count;
        !          1282: 
        !          1283:        /*
        !          1284:         * Adjust swap_{start,stop}_pageout_rate to the paging rate peak.
        !          1285:         * This is an attempt to find the optimum paging rates at which
        !          1286:         * to trigger task swapping on or off to regulate paging activity,
        !          1287:         * depending on the hardware capacity.
        !          1288:         */
        !          1289:        if (vm_pageout_rate_avg > vm_pageout_rate_peakavg) {
        !          1290:                unsigned int desired_max;
        !          1291: 
        !          1292:                vm_pageout_rate_peakavg = vm_pageout_rate_avg;
        !          1293:                swap_start_pageout_rate =
        !          1294:                        vm_pageout_rate_peakavg * swap_pageout_high_water_mark / 100;
        !          1295:                swap_stop_pageout_rate = 
        !          1296:                        vm_pageout_rate_peakavg * swap_pageout_low_water_mark / 100;
        !          1297:        }
        !          1298: 
        !          1299: #if    TASK_SW_DEBUG
        !          1300:        /*
        !          1301:         * For measurements, allow fixed values.
        !          1302:         */
        !          1303:        if (fixed_swap_start_pageout_rate)
        !          1304:                swap_start_pageout_rate = fixed_swap_start_pageout_rate;
        !          1305:        if (fixed_swap_stop_pageout_rate)
        !          1306:                swap_stop_pageout_rate = fixed_swap_stop_pageout_rate;
        !          1307: #endif /* TASK_SW_DEBUG */
        !          1308: 
        !          1309: #if    TASK_SW_DEBUG
        !          1310:        if (task_swap_stats)
        !          1311:                printf("vm_avgs: pageout_rate: %d %d (on/off: %d/%d); page_free: %d %d (tgt: %d)\n",
        !          1312:                       vm_pageout_rate_avg / AVE_SCALE,
        !          1313:                       vm_pageout_rate_longavg / AVE_SCALE,
        !          1314:                       swap_start_pageout_rate / AVE_SCALE,
        !          1315:                       swap_stop_pageout_rate / AVE_SCALE,
        !          1316:                       vm_page_free_avg / AVE_SCALE,
        !          1317:                       vm_page_free_longavg / AVE_SCALE,
        !          1318:                       vm_page_free_target);
        !          1319: #endif /* TASK_SW_DEBUG */
        !          1320:        
        !          1321:        if (vm_page_free_avg / AVE_SCALE <= vm_page_free_target) {
        !          1322:                if (task_swap_on) {
        !          1323:                        /* The following is a delicate attempt to balance the
        !          1324:                         * need for reasonably rapid response to system
        !          1325:                         * thrashing, with the equally important desire to
        !          1326:                         * prevent the onset of swapping simply because of a
        !          1327:                         * short burst of paging activity.
        !          1328:                         */
        !          1329:                        if ((vm_pageout_rate_longavg > swap_stop_pageout_rate) &&
        !          1330:                            (vm_pageout_rate_avg > swap_start_pageout_rate) ||
        !          1331:                            (vm_pageout_rate_avg > vm_pageout_rate_peakavg) ||
        !          1332:                            (vm_grab_rate_avg > max_grab_rate))
        !          1333:                                wake_task_swapper(FALSE);
        !          1334:                }
        !          1335:        } else /* page demand is low; should consider swapin */ {
        !          1336:                if (tasks_swapped_out != 0)
        !          1337:                        wake_task_swapper(TRUE);
        !          1338:        }
        !          1339: }
        !          1340: 
        !          1341: void
        !          1342: task_swapout_eligible(task_t task)
        !          1343: {
        !          1344: #if    TASK_SW_DEBUG
        !          1345:        task_swapper_lock();
        !          1346:        if (task_swap_debug && on_swapped_list(task)) {
        !          1347:                printf("swapout_eligible: task 0x%X on swapped list\n", task);
        !          1348:                Debugger("");
        !          1349:        }
        !          1350:        task_swapper_unlock();
        !          1351: #endif
        !          1352:        task_swapout_lock();
        !          1353:        task_lock(task);
        !          1354: #if    TASK_SW_DEBUG
        !          1355:        if (task->swap_flags & TASK_SW_ELIGIBLE) {
        !          1356:                printf("swapout_eligible: task 0x%X already eligible\n", task);
        !          1357:        }
        !          1358: #endif /* TASK_SW_DEBUG */
        !          1359:        if ((task->swap_state == TASK_SW_IN) &&
        !          1360:            ((task->swap_flags & TASK_SW_ELIGIBLE) == 0)) {
        !          1361:                queue_enter(&eligible_tasks,task,task_t,swapped_tasks);
        !          1362:                task->swap_flags |= TASK_SW_ELIGIBLE;
        !          1363:        }
        !          1364:        task_unlock(task);
        !          1365:        task_swapout_unlock();
        !          1366: }
        !          1367: 
        !          1368: void
        !          1369: task_swapout_ineligible(task_t task)
        !          1370: {
        !          1371: #if    TASK_SW_DEBUG
        !          1372:        task_swapper_lock();
        !          1373:        if (task_swap_debug && on_swapped_list(task)) {
        !          1374:                printf("swapout_ineligible: task 0x%X on swapped list\n", task);
        !          1375:                Debugger("");
        !          1376:        }
        !          1377:        task_swapper_unlock();
        !          1378: #endif
        !          1379:        task_swapout_lock();
        !          1380:        task_lock(task);
        !          1381: #if    TASK_SW_DEBUG
        !          1382:        if (!(task->swap_flags & TASK_SW_ELIGIBLE))
        !          1383:                printf("swapout_ineligible: task 0x%X already inel.\n", task);
        !          1384: #endif /* TASK_SW_DEBUG */
        !          1385:        if ((task->swap_state != TASK_SW_IN) && 
        !          1386:            (task->swap_flags & TASK_SW_ELIGIBLE)) {
        !          1387:                queue_remove(&eligible_tasks, task, task_t, swapped_tasks);
        !          1388:                task->swap_flags &= ~TASK_SW_ELIGIBLE;
        !          1389:        }
        !          1390:        task_unlock(task);
        !          1391:        task_swapout_unlock();
        !          1392: }
        !          1393: 
        !          1394: int task_swap_ast_aborted = 0;
        !          1395: 
        !          1396: /*
        !          1397:  *     Process an AST_SWAPOUT.
        !          1398:  */
        !          1399: void
        !          1400: swapout_ast()
        !          1401: {
        !          1402:        spl_t           s;
        !          1403:        thread_act_t    act;
        !          1404:        thread_t        thread;
        !          1405: 
        !          1406:        act = current_act();
        !          1407: 
        !          1408:        /*
        !          1409:         * Task is being swapped out.  First mark it as suspended
        !          1410:         * and halted, then call thread_swapout_enqueue to put
        !          1411:         * the thread on the queue for task_swap_swapout_threads
        !          1412:         * to swap out the thread.
        !          1413:         */
        !          1414:        /*
        !          1415:         * Don't swap unswappable threads
        !          1416:         */
        !          1417:        thread = act_lock_thread(act);
        !          1418:        s = splsched();
        !          1419:        if (thread)
        !          1420:                thread_lock(thread);
        !          1421:        if ((act->ast & AST_SWAPOUT) == 0) {
        !          1422:                /*
        !          1423:                 * Race with task_swapin. Abort swapout.
        !          1424:                 */
        !          1425:                task_swap_ast_aborted++;        /* not locked XXX */
        !          1426:                if (thread)
        !          1427:                        thread_unlock(thread);
        !          1428:                splx(s);
        !          1429:                act_unlock_thread(act);
        !          1430:        } else if (act->swap_state == TH_SW_IN) {
        !          1431:                /*
        !          1432:                 * Mark swap_state as TH_SW_TASK_SWAPPING to avoid
        !          1433:                 * race with thread swapper, which will only
        !          1434:                 * swap thread if swap_state is TH_SW_IN.
        !          1435:                 * This way, the thread can only be swapped by
        !          1436:                 * the task swapping mechanism.
        !          1437:                 */
        !          1438:                act->swap_state |= TH_SW_TASK_SWAPPING;
        !          1439:                /* assert(act->suspend_count == 0); XXX ? */
        !          1440:                if (thread)
        !          1441:                        thread_unlock(thread);
        !          1442:                if (act->suspend_count++ == 0)  /* inline thread_hold */
        !          1443:                        install_special_handler(act);
        !          1444:                /* self->state |= TH_HALTED; */
        !          1445:                thread_ast_clear(act, AST_SWAPOUT);
        !          1446:                /*
        !          1447:                 * Initialize the swap_queue fields to allow an extra
        !          1448:                 * queue_remove() in task_swapin if we lose the race
        !          1449:                 * (task_swapin can be called before we complete
        !          1450:                 * thread_swapout_enqueue).
        !          1451:                 */
        !          1452:                queue_init((queue_t) &act->swap_queue);
        !          1453:                splx(s);
        !          1454:                act_unlock_thread(act);
        !          1455:                /* this must be called at normal interrupt level */
        !          1456:                thread_swapout_enqueue(act);
        !          1457:        } else {
        !          1458:                /* thread isn't swappable; continue running */
        !          1459:                assert(act->swap_state == TH_SW_UNSWAPPABLE);
        !          1460:                if (thread)
        !          1461:                        thread_unlock(thread);
        !          1462:                thread_ast_clear(act, AST_SWAPOUT);
        !          1463:                splx(s);
        !          1464:                act_unlock_thread(act);
        !          1465:        }
        !          1466: }
        !          1467: 
        !          1468: #endif /* TASK_SWAPPER */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.