Return to zalloc.c CVS log

Up to [Apple Darwin 0.x] / kernel / kern

Annotation of kernel/kern/zalloc.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
        !             7:  * Reserved.  This file contains Original Code and/or Modifications of
        !             8:  * Original Code as defined in and that are subject to the Apple Public
        !             9:  * Source License Version 1.1 (the "License").  You may not use this file
        !            10:  * except in compliance with the License.  Please obtain a copy of the
        !            11:  * License at http://www.apple.com/publicsource and read it before using
        !            12:  * this file.
        !            13:  * 
        !            14:  * The Original Code and all software distributed under the License are
        !            15:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            16:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            17:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            18:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            19:  * License for the specific language governing rights and limitations
        !            20:  * under the License.
        !            21:  * 
        !            22:  * @APPLE_LICENSE_HEADER_END@
        !            23:  */
        !            24: 
        !            25: /* 
        !            26:  * Mach Operating System
        !            27:  * Copyright (c) 1993,1991,1990,1989,1988,1987 Carnegie Mellon University
        !            28:  * All Rights Reserved.
        !            29:  * 
        !            30:  * Permission to use, copy, modify and distribute this software and its
        !            31:  * documentation is hereby granted, provided that both the copyright
        !            32:  * notice and this permission notice appear in all copies of the
        !            33:  * software, derivative works or modified versions, and any portions
        !            34:  * thereof, and that both notices appear in supporting documentation.
        !            35:  * 
        !            36:  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
        !            37:  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
        !            38:  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
        !            39:  * 
        !            40:  * Carnegie Mellon requests users of this software to return to
        !            41:  * 
        !            42:  *  Software Distribution Coordinator  or  [email protected]
        !            43:  *  School of Computer Science
        !            44:  *  Carnegie Mellon University
        !            45:  *  Pittsburgh PA 15213-3890
        !            46:  * 
        !            47:  * any improvements or extensions that they make and grant Carnegie Mellon
        !            48:  * the rights to redistribute these changes.
        !            49:  */
        !            50: /*
        !            51:  * Copyright (c) 1995, 1997 Apple Computer, Inc.
        !            52:  *
        !            53:  * HISTORY
        !            54:  *
        !            55:  * 23 June 1995 ? at NeXT
        !            56:  *     Pulled over from CMU (MK83), added local
        !            57:  *     mods: freespace suballocator and sorted
        !            58:  *     zone free lists to reduce fragmentation.
        !            59:  */
        !            60: /*
        !            61:  *     File:   kern/zalloc.c
        !            62:  *     Author: Avadis Tevanian, Jr.
        !            63:  *
        !            64:  *     Zone-based memory allocator.  A zone is a collection of fixed size
        !            65:  *     data blocks for which quick allocation/deallocation is possible.
        !            66:  */
        !            67:  
        !            68: #import <mach/features.h>
        !            69: 
        !            70: #include <kern/macro_help.h>
        !            71: #include <kern/sched.h>
        !            72: #include <kern/time_out.h>
        !            73: #include <kern/zalloc.h>
        !            74: #include <mach/vm_param.h>
        !            75: #include <vm/vm_kern.h>
        !            76: 
        !            77: #if    MACH_DEBUG
        !            78: #include <mach/kern_return.h>
        !            79: #include <mach/machine/vm_types.h>
        !            80: #include <mach_debug/zone_info.h>
        !            81: #include <kern/host.h>
        !            82: #include <vm/vm_map.h>
        !            83: #include <vm/vm_user.h>
        !            84: #include <vm/vm_kern.h>
        !            85: #endif
        !            86: 
        !            87: #define ADD_TO_ZONE(zone, element)                                     \
        !            88: MACRO_BEGIN                                                            \
        !            89:        vm_offset_t     cur, *last;                                     \
        !            90:                if (            (zone)->last_insert != 0        &&      \
        !            91:                                (element) > (zone)->last_insert )       \
        !            92:                        (vm_offset_t)last = (zone)->last_insert;        \
        !            93:                else                                                    \
        !            94:                        last = &(zone)->free_elements;                  \
        !            95:                while (         (cur = *last) != 0      &&              \
        !            96:                                (element) > cur         )               \
        !            97:                        (vm_offset_t)last = cur;                        \
        !            98:                *(vm_offset_t *)(element) = cur;                        \
        !            99:                *last = (element);                                      \
        !           100:                (zone)->last_insert = (element);                        \
        !           101:                (zone)->count--;                                        \
        !           102: MACRO_END
        !           103: 
        !           104: #define REMOVE_FROM_ZONE(zone, ret, type)                              \
        !           105: MACRO_BEGIN                                                            \
        !           106:        (ret) = (type) (zone)->free_elements;                           \
        !           107:        if ((ret) != (type) 0) {                                        \
        !           108:                (zone)->count++;                                        \
        !           109:                (zone)->free_elements = *(vm_offset_t *)(ret);          \
        !           110:                if ((zone)->last_insert == (vm_offset_t)(ret))          \
        !           111:                        (zone)->last_insert = 0;                        \
        !           112:        }                                                               \
        !           113: MACRO_END
        !           114: 
        !           115: zone_t         zone_zone;      /* this is the zone containing other zones */
        !           116: 
        !           117: boolean_t      zone_ignore_overflow = TRUE;
        !           118: 
        !           119: vm_map_t       zone_map = VM_MAP_NULL;
        !           120: vm_size_t      zone_map_size;
        !           121: vm_size_t      zone_map_size_min = 12 * 1024 * 1024;
        !           122: vm_size_t      zone_map_size_max = 128 * 1024 * 1024;
        !           123: vm_offset_t    zone_min, zone_max;
        !           124: 
        !           125: /*
        !           126:  *     The VM system gives us an initial chunk of memory.
        !           127:  *     It has to be big enough to allocate the zone_zone
        !           128:  *     and some initial kernel data structures, like kernel maps.
        !           129:  *     It is advantageous to make it bigger than really necessary,
        !           130:  *     because this memory is more efficient than normal kernel
        !           131:  *     virtual memory.  (It doesn't have vm_page structures backing it
        !           132:  *     and it may have other machine-dependent advantages.)
        !           133:  *     So for best performance, zdata_size should approximate
        !           134:  *     the amount of memory you expect the zone system to consume.
        !           135:  */
        !           136: 
        !           137: vm_offset_t    zdata;
        !           138: vm_size_t      zdata_size = 512 * 1024;
        !           139: 
        !           140: #define lock_zone(zone)                                        \
        !           141: MACRO_BEGIN                                            \
        !           142:        if ((zone)->pageable) {                         \
        !           143:                lock_write(&(zone)->complex_lock);      \
        !           144:        } else {                                        \
        !           145:                spl_t s = splhigh();                    \
        !           146:                simple_lock(&(zone)->lock);             \
        !           147:                (zone)->lock_ipl = s;                   \
        !           148:        }                                               \
        !           149: MACRO_END
        !           150: 
        !           151: #define unlock_zone(zone)                              \
        !           152: MACRO_BEGIN                                            \
        !           153:        if ((zone)->pageable) {                         \
        !           154:                lock_done(&(zone)->complex_lock);       \
        !           155:        } else {                                        \
        !           156:                spl_t s = (zone)->lock_ipl;             \
        !           157:                simple_unlock(&(zone)->lock);           \
        !           158:                splx(s);                                \
        !           159:        }                                               \
        !           160: MACRO_END
        !           161: 
        !           162: #define lock_zone_init(zone)                           \
        !           163: MACRO_BEGIN                                            \
        !           164:        if ((zone)->pageable) {                         \
        !           165:                lock_init(&(zone)->complex_lock, TRUE); \
        !           166:        } else {                                        \
        !           167:                simple_lock_init(&(zone)->lock);        \
        !           168:        }                                               \
        !           169: MACRO_END
        !           170: 
        !           171: vm_offset_t zget_space(
        !           172:        struct zone_free_space  *free_space,
        !           173:        vm_size_t               size,
        !           174:        boolean_t               canblock);
        !           175: 
        !           176: decl_simple_lock_data(,zget_space_lock)
        !           177: 
        !           178: /*
        !           179:  * A free list entry, which is created
        !           180:  * at the front of an available region
        !           181:  * of memory.  The 'pred' field points
        !           182:  * at the 'next' pointer of the previous
        !           183:  * entry (or the head pointer).
        !           184:  */
        !           185: struct zone_free_space_entry {
        !           186:        struct zone_free_space_entry    *next;
        !           187:        vm_size_t                       length;
        !           188:        struct zone_free_space_entry    **pred;
        !           189:        int                             _pad[1];
        !           190: };
        !           191: #define ZONE_MIN_ALLOC         16      /*
        !           192:                                         * *Must* be:
        !           193:                                         *  a power of two
        !           194:                                         *      and
        !           195:                                         *  at least sizeof (struct
        !           196:                                         * zone_free_space_entry)
        !           197:                                         */
        !           198: 
        !           199: /*
        !           200:  * An entry in the free list hint table,
        !           201:  * which allows for quickly locating a
        !           202:  * suitably sized region needed to satisfy
        !           203:  * a request.
        !           204:  */
        !           205: struct zone_free_space_hint {
        !           206:        struct zone_free_space_entry    *entry;
        !           207:        int                             _pad[3];
        !           208: };
        !           209: 
        !           210: /*
        !           211:  * Structure used to manage memory which
        !           212:  * has been obtained from the system, but
        !           213:  * which is not currently owned by any zone.
        !           214:  * The main two parameters are 'alloc_unit'
        !           215:  * and 'alloc_max'.  The former specifies the
        !           216:  * allocation granularity.  Allocation requests
        !           217:  * will be rounded up to this size, which must
        !           218:  * be a power of two.  The size of the largest
        !           219:  * (suggested) allocation request is specified
        !           220:  * by 'alloc_max'.  The free list is headed by
        !           221:  * 'entries', and is a doubly linked list of
        !           222:  * free regions, sorted by ascending address.
        !           223:  * There also is a table of hints, indexed by
        !           224:  * region size, which is used to speed up the
        !           225:  * allocations when the free list becomes
        !           226:  * especially large.  It contains one entry
        !           227:  * per size value between alloc_unit and alloc_max.
        !           228:  */ 
        !           229: struct zone_free_space {
        !           230:        vm_size_t                       alloc_unit;
        !           231:        vm_size_t                       alloc_max;
        !           232:        struct zone_free_space_entry    *entries;
        !           233:        integer_t                       num_entries;
        !           234:        integer_t                       hash_shift;
        !           235:        struct zone_free_space_hint     *hints;
        !           236:        integer_t                       num_hints;
        !           237: };
        !           238: 
        !           239: struct zone_free_space         *zone_free_space[8];
        !           240: integer_t                      zone_free_space_count;
        !           241: 
        !           242: /*
        !           243:  * There is a default allocation space (zone_free_space[0]),
        !           244:  * which is special.  It is statically allocated, contains
        !           245:  * a single hint, and space is not reclaimed from it.  It
        !           246:  * is used to allocate space for non collectable zones,
        !           247:  * as well as resources needed for bootstrapping purposes.
        !           248:  */
        !           249: struct zone_free_space_hint    _zone_default_space_hint;
        !           250: struct zone_free_space         _zone_default_space;
        !           251: #define        zone_default_space      (&_zone_default_space)
        !           252: 
        !           253: static void zone_free_space_select(zone_t      zone);
        !           254: 
        !           255: #define zone_collectable(z)    ((z)->free_space != 0 && \
        !           256:                                        (z)->free_space != zone_default_space)
        !           257: 
        !           258: /*
        !           259:  * Compute the hash address for an element
        !           260:  * of a particular size.  Oversized requests
        !           261:  * all land in the last bucket.
        !           262:  */
        !           263: static __inline__
        !           264: integer_t
        !           265: zone_free_space_hash(
        !           266:        struct zone_free_space          *freespace,
        !           267:        vm_size_t                       size
        !           268: )
        !           269: {
        !           270:        integer_t               hash;
        !           271:        
        !           272:        if ((hash = size >> freespace->hash_shift) >
        !           273:                                        freespace->num_hints)
        !           274:                return (freespace->num_hints);
        !           275:        else
        !           276:                return (hash);
        !           277: }
        !           278: #define        zone_free_space_hint_from_hash(freespace, hash) \
        !           279:                                        ((freespace)->hints + (hash) - 1)
        !           280: 
        !           281: /*
        !           282:  * Return the hint entry for an element of
        !           283:  * a particular size.
        !           284:  */
        !           285: static __inline__
        !           286: struct zone_free_space_hint *
        !           287: zone_free_space_hint(
        !           288:        struct zone_free_space          *freespace,
        !           289:        vm_size_t                       size
        !           290: )
        !           291: {
        !           292:        return zone_free_space_hint_from_hash(freespace,
        !           293:                                        zone_free_space_hash(freespace, size));
        !           294: }
        !           295: 
        !           296: /*
        !           297:  * Conditionally insert the entry into the
        !           298:  * hint table such that the hint indicates
        !           299:  * the lowest addressed entry of the particular
        !           300:  * size.
        !           301:  */
        !           302: static __inline__
        !           303: void
        !           304: zone_free_space_hint_insert(
        !           305:        struct zone_free_space          *freespace,
        !           306:        struct zone_free_space_entry    *entry
        !           307: )
        !           308: {
        !           309:        struct zone_free_space_hint     *hint;
        !           310: 
        !           311:        hint = zone_free_space_hint(freespace, entry->length);
        !           312:        if (hint->entry == 0 || entry < hint->entry)
        !           313:                hint->entry = entry;
        !           314: }
        !           315: 
        !           316: /*
        !           317:  * Delete the entry from the hint table (if
        !           318:  * present), and locate the next entry of the
        !           319:  * particular size by searching forwards in
        !           320:  * the free list.  For the 'alloc_max' hint,
        !           321:  * we choose the next entry of size >= alloc_max.
        !           322:  */
        !           323: static
        !           324: void
        !           325: zone_free_space_hint_delete(
        !           326:        struct zone_free_space          *freespace,
        !           327:        struct zone_free_space_entry    *entry
        !           328: )
        !           329: {
        !           330:        integer_t                       hash;
        !           331:        struct zone_free_space_hint     *hint;
        !           332: 
        !           333:        hash = zone_free_space_hash(freespace, entry->length);
        !           334:        hint = zone_free_space_hint_from_hash(freespace, hash);
        !           335: 
        !           336:        if (entry == hint->entry) {
        !           337:                if (hash < freespace->num_hints) {
        !           338:                        struct zone_free_space_entry
        !           339:                                        *cur, **last = &entry->next;
        !           340: 
        !           341:                        while ((cur = *last) != 0 &&
        !           342:                                        cur->length != entry->length)
        !           343:                                last = &cur->next;
        !           344: 
        !           345:                        hint->entry = cur;
        !           346:                }
        !           347:                else {
        !           348:                        struct zone_free_space_entry
        !           349:                                        *cur, **last = &entry->next;
        !           350: 
        !           351:                        while ((cur = *last) != 0 &&
        !           352:                                        cur->length < freespace->alloc_max)
        !           353:                                last = &cur->next;
        !           354: 
        !           355:                        hint->entry = cur;
        !           356:                }
        !           357:        }
        !           358: }
        !           359: 
        !           360: /*
        !           361:  * Update the hint for an entry which has been
        !           362:  * expanded from the front.  In this case, the
        !           363:  * header has moved (and is no longer valid),
        !           364:  * so we need both the length and the address
        !           365:  * of the old entry.  This could be accomplished
        !           366:  * with separate delete/insert operations, but
        !           367:  * this is much more efficient for several
        !           368:  * important cases.
        !           369:  */
        !           370: static
        !           371: void
        !           372: zone_free_space_hint_prepend(
        !           373:        struct zone_free_space          *freespace,
        !           374:        struct zone_free_space_entry    *entry,
        !           375:        vm_size_t                       old_length,
        !           376:        void                            *old_entry
        !           377: )
        !           378: {
        !           379:        integer_t                       old_hash, new_hash;
        !           380:        struct zone_free_space_hint     *hint;
        !           381: 
        !           382:        /*
        !           383:         * Calculate both the new and the old hash
        !           384:         * addresses, as well as the old hint structure,
        !           385:         * which we are likely to need.
        !           386:         */
        !           387:        new_hash = zone_free_space_hash(freespace, entry->length);
        !           388:        old_hash = zone_free_space_hash(freespace, old_length);
        !           389:        hint = zone_free_space_hint_from_hash(freespace, old_hash);
        !           390: 
        !           391:        /*
        !           392:         * Hash address has changed.
        !           393:         */
        !           394:        if (old_hash != new_hash) {
        !           395:                /*
        !           396:                 * Old hint was valid, update it.
        !           397:                 */
        !           398:                if (old_entry == hint->entry) {
        !           399:                        if (old_hash < freespace->num_hints) {
        !           400:                                struct zone_free_space_entry
        !           401:                                                *cur, **last = &entry->next;
        !           402: 
        !           403:                                while ((cur = *last) != 0 &&
        !           404:                                                cur->length != old_length)
        !           405:                                        last = &cur->next;
        !           406: 
        !           407:                                hint->entry = cur;
        !           408:                        }
        !           409:                        else {
        !           410:                                struct zone_free_space_entry
        !           411:                                                *cur, **last = &entry->next;
        !           412: 
        !           413:                                while ((cur = *last) != 0 &&
        !           414:                                                cur->length < 
        !           415:                                                        freespace->alloc_max)
        !           416:                                        last = &cur->next;
        !           417: 
        !           418:                                hint->entry = cur;
        !           419:                        }
        !           420:                }
        !           421: 
        !           422:                /*
        !           423:                 * Insert a hint for the new entry.
        !           424:                 */
        !           425:                hint = zone_free_space_hint_from_hash(freespace, new_hash);
        !           426:                if (hint->entry == 0 || entry < hint->entry)
        !           427:                        hint->entry = entry;
        !           428:        }
        !           429:        /*
        !           430:         * If the hash address has not
        !           431:         * changed, always replace a valid
        !           432:         * old hint with the new one.
        !           433:         */
        !           434:        else if (old_entry == hint->entry)
        !           435:                hint->entry = entry;
        !           436: }
        !           437: 
        !           438: /*
        !           439:  * Update the hint for an entry which has been
        !           440:  * expanded on the end.  This could be accomplished
        !           441:  * with separate delete/insert operations, but
        !           442:  * this is much more efficient for several
        !           443:  * important cases.
        !           444:  */
        !           445: static
        !           446: void
        !           447: zone_free_space_hint_append(
        !           448:        struct zone_free_space          *freespace,
        !           449:        struct zone_free_space_entry    *entry,
        !           450:        vm_size_t                       old_length
        !           451: )
        !           452: {
        !           453:        integer_t                       old_hash, new_hash;
        !           454:        struct zone_free_space_hint     *hint;
        !           455: 
        !           456:        /*
        !           457:         * Calculate both the new and the old hash
        !           458:         * addresses.
        !           459:         */
        !           460:        new_hash = zone_free_space_hash(freespace, entry->length);
        !           461:        old_hash = zone_free_space_hash(freespace, old_length);
        !           462: 
        !           463:        if (old_hash != new_hash) {
        !           464:                hint = zone_free_space_hint_from_hash(freespace, old_hash);
        !           465:                /*
        !           466:                 * Old hint was valid, update it.
        !           467:                 */
        !           468:                if (entry == hint->entry) {
        !           469:                        if (old_hash < freespace->num_hints) {
        !           470:                                struct zone_free_space_entry
        !           471:                                                *cur, **last = &entry->next;
        !           472: 
        !           473:                                while ((cur = *last) != 0 &&
        !           474:                                                cur->length != old_length)
        !           475:                                        last = &cur->next;
        !           476: 
        !           477:                                hint->entry = cur;
        !           478:                        }
        !           479:                        else {
        !           480:                                struct zone_free_space_entry
        !           481:                                                *cur, **last = &entry->next;
        !           482: 
        !           483:                                while ((cur = *last) != 0 &&
        !           484:                                                cur->length < 
        !           485:                                                        freespace->alloc_max)
        !           486:                                        last = &cur->next;
        !           487: 
        !           488:                                hint->entry = cur;
        !           489:                        }
        !           490:                }
        !           491: 
        !           492:                /*
        !           493:                 * Insert a hint for the new entry.
        !           494:                 */
        !           495:                hint = zone_free_space_hint_from_hash(freespace, new_hash);
        !           496:                if (hint->entry == 0 || entry < hint->entry)
        !           497:                        hint->entry = entry;
        !           498:        }
        !           499: }
        !           500: 
        !           501: /*
        !           502:  * Locate a suitably sized entry, using the
        !           503:  * allocation hints.  The entry is removed
        !           504:  * from the hint table, which is also updated
        !           505:  * accordingly.  The entry's position in the
        !           506:  * free list is not affected.
        !           507:  */
        !           508: static
        !           509: struct zone_free_space_entry *
        !           510: zone_free_space_lookup(
        !           511:        struct zone_free_space          *freespace,
        !           512:        vm_size_t                       size
        !           513: )
        !           514: {
        !           515:        integer_t                       hash;
        !           516:        struct zone_free_space_hint     *hint;
        !           517:        struct zone_free_space_entry    *entry;
        !           518: 
        !           519:        /*
        !           520:         * Perform a couple of quick checks:
        !           521:         * 1) an empty free list or
        !           522:         * 2) a suitable first entry
        !           523:         */
        !           524:        if ((entry = freespace->entries) == 0)
        !           525:                return (entry);
        !           526:        else if (entry->length >= size) {
        !           527:                zone_free_space_hint_delete(freespace, entry);
        !           528:                
        !           529:                return (entry);
        !           530:        }
        !           531: 
        !           532:        /*
        !           533:         * Calculate the hash address and hint
        !           534:         * entry corresponding to the request
        !           535:         * size.  We start there and move on to
        !           536:         * the larger hints if needed.
        !           537:         */
        !           538:        hash = zone_free_space_hash(freespace, size); 
        !           539:        hint = zone_free_space_hint_from_hash(freespace, hash);
        !           540: 
        !           541:        /*
        !           542:         * This loop checks the exact sized hints
        !           543:         * (hash to [num_hints - 1]).  If we encounter
        !           544:         * a valid hint, we return that entry, after
        !           545:         * first searching ahead in the free list to
        !           546:         * replace it.  If we come to the end of
        !           547:         * the free list while searching, we end up
        !           548:         * invalidating this hint.
        !           549:         */
        !           550:        while (hash < freespace->num_hints) {
        !           551:                if ((entry = hint->entry) != 0) {
        !           552:                        struct zone_free_space_entry
        !           553:                                        *cur, **last = &entry->next;
        !           554: 
        !           555:                        while ((cur = *last) != 0 &&
        !           556:                                        cur->length != entry->length)
        !           557:                                last = &cur->next;
        !           558: 
        !           559:                        hint->entry = cur;
        !           560:                        
        !           561:                        return (entry);
        !           562:                }
        !           563:                
        !           564:                hash++; hint++;
        !           565:        }
        !           566: 
        !           567:        /*
        !           568:         * Now check the last bucket.
        !           569:         */
        !           570:        if ((entry = hint->entry) != 0) {
        !           571:                struct zone_free_space_entry
        !           572:                                *cur, **last = &entry->next;
        !           573: 
        !           574:                /*
        !           575:                 * The last bucket contains the lowest
        !           576:                 * addressed entry >= alloc_max, which
        !           577:                 * isn't necessarily big enough for this
        !           578:                 * request.  If it isn't big enough, then
        !           579:                 * search ahead in the free list for a
        !           580:                 * suitable entry to return.  In this case
        !           581:                 * we also leave the current hint alone
        !           582:                 * since we aren't going to use it.
        !           583:                 */
        !           584:                if (entry->length < size) {
        !           585:                        while ((cur = *last) != 0 &&
        !           586:                                        cur->length < size)
        !           587:                                last = &cur->next;
        !           588:                                
        !           589:                        return (cur);
        !           590:                }
        !           591: 
        !           592:                while ((cur = *last) != 0 &&
        !           593:                                cur->length < freespace->alloc_max)
        !           594:                        last = &cur->next;
        !           595: 
        !           596:                hint->entry = cur;
        !           597:        }
        !           598:        
        !           599:        return (entry);
        !           600: }
        !           601: 
        !           602: /*
        !           603:  *     Protects first_zone, last_zone, num_zones,
        !           604:  *     and the next_zone field of zones.
        !           605:  */
        !           606: decl_simple_lock_data(,all_zones_lock)
        !           607: zone_t                 first_zone;
        !           608: zone_t                 *last_zone;
        !           609: int                    num_zones;
        !           610: 
        !           611: /*
        !           612:  *     zinit initializes a new zone.  The zone data structures themselves
        !           613:  *     are stored in a zone, which is initially a static structure that
        !           614:  *     is initialized by zone_init.
        !           615:  */
        !           616: zone_t zinit(size, max, alloc, pageable, name)
        !           617:        vm_size_t       size;           /* the size of an element */
        !           618:        vm_size_t       max;            /* maximum memory to use */
        !           619:        vm_size_t       alloc;          /* allocation size */
        !           620:        boolean_t       pageable;       /* is this zone pageable? */
        !           621:        char            *name;          /* a name for the zone */
        !           622: {
        !           623:        register zone_t         z;
        !           624: 
        !           625:        if (zone_zone == ZONE_NULL)
        !           626:                z = (zone_t) zget_space(
        !           627:                                zone_default_space,
        !           628:                                sizeof(struct zone),
        !           629:                                FALSE);
        !           630:        else
        !           631:                z = (zone_t) zalloc(zone_zone);
        !           632:        if (z == ZONE_NULL)
        !           633:                panic("zinit");
        !           634: 
        !           635:        if (alloc == 0)
        !           636:                alloc = PAGE_SIZE;
        !           637: 
        !           638:        if (size == 0)
        !           639:                size = sizeof(z->free_elements);
        !           640: 
        !           641:        size = ((size + (ZONE_MIN_ALLOC - 1)) & ~(ZONE_MIN_ALLOC - 1));
        !           642: 
        !           643:        /*
        !           644:         *      Round off all the parameters appropriately.
        !           645:         */
        !           646: 
        !           647:        if ((max = round_page(max)) < (alloc = round_page(alloc)))
        !           648:                max = alloc;
        !           649: 
        !           650:        z->last_insert = z->free_elements = 0;
        !           651:        z->cur_size = 0;
        !           652:        z->max_size = max;
        !           653:        z->elem_size = size;
        !           654: 
        !           655:        z->alloc_size = alloc;
        !           656:        z->pageable = pageable;
        !           657:        z->zone_name = name;
        !           658:        z->count = 0;
        !           659:        z->doing_alloc = FALSE;
        !           660:        z->exhaustible = z->sleepable = FALSE;
        !           661:        z->expandable  = TRUE;
        !           662:        lock_zone_init(z);
        !           663:        zone_free_space_select(z);
        !           664: 
        !           665:        /*
        !           666:         *      Add the zone to the all-zones list.
        !           667:         */
        !           668: 
        !           669:        z->next_zone = ZONE_NULL;
        !           670:        simple_lock(simple_lock_addr(all_zones_lock));
        !           671:        *last_zone = z;
        !           672:        last_zone = &z->next_zone;
        !           673:        num_zones++;
        !           674:        simple_unlock(simple_lock_addr(all_zones_lock));
        !           675: 
        !           676:        return(z);
        !           677: }
        !           678: 
        !           679: /*
        !           680:  *     Cram the given memory into the specified zone.
        !           681:  */
        !           682: void zcram(zone, newmem, size)
        !           683:        register zone_t         zone;
        !           684:        vm_offset_t             newmem;
        !           685:        vm_size_t               size;
        !           686: {
        !           687:        register vm_size_t      elem_size;
        !           688: 
        !           689:        if (newmem == (vm_offset_t) 0) {
        !           690:                panic("zcram - memory at zero");
        !           691:        }
        !           692:        elem_size = zone->elem_size;
        !           693: 
        !           694:        lock_zone(zone);
        !           695:        while (size >= elem_size) {
        !           696:                ADD_TO_ZONE(zone, newmem);
        !           697:                zone->count++;  /* compensate for ADD_TO_ZONE */
        !           698:                size -= elem_size;
        !           699:                newmem += elem_size;
        !           700:                zone->cur_size += elem_size;
        !           701:        }
        !           702:        unlock_zone(zone);
        !           703: }
        !           704: 
        !           705: /*
        !           706:  * Allocate (return) a new zone element from a new memory
        !           707:  * region.  Remaining memory from the new region is added
        !           708:  * to the specified freelist.  Before generating the new 
        !           709:  * element, an attempt is made to combine the new region
        !           710:  * with an existing entry.  New elements are always taken
        !           711:  * from the front of a free region.
        !           712:  */
        !           713: vm_offset_t zone_free_space_add(freespace, size, new_space, space_to_add)
        !           714:        struct zone_free_space *freespace;
        !           715:        vm_size_t size;
        !           716:        vm_offset_t new_space;
        !           717:        vm_size_t space_to_add;
        !           718: {
        !           719:        struct zone_free_space_entry    *cur, **last;
        !           720: 
        !           721:        if (freespace == 0)
        !           722:                freespace = zone_default_space;
        !           723: 
        !           724:        /*
        !           725:         * Search the free list for an existing
        !           726:         * abutting entry.
        !           727:         */
        !           728:        last = &freespace->entries;
        !           729:        while ((cur = *last) != 0 &&
        !           730:                        (vm_offset_t)cur < new_space &&
        !           731:                        ((vm_offset_t)cur + cur->length) != new_space)
        !           732:                last = &cur->next;
        !           733:                        
        !           734:        if (cur == 0 || ((vm_offset_t)cur + cur->length) < new_space) {
        !           735:                /*
        !           736:                 * No entry was found to combine with.
        !           737:                 * Take the new element from the front
        !           738:                 * of the new region, and insert the
        !           739:                 * remainder as a new entry.
        !           740:                 */
        !           741:                if ((space_to_add - size) >= ZONE_MIN_ALLOC) {
        !           742:                        /*
        !           743:                         * If we are not at the end of
        !           744:                         * the free list, then insert the
        !           745:                         * new entry after the current entry.
        !           746:                         */
        !           747:                        if (cur != 0)
        !           748:                                last = &cur->next;
        !           749:                        (vm_offset_t)cur = new_space + size;
        !           750:                        cur->length = space_to_add - size;
        !           751:                        if (cur->next = *last)
        !           752:                                cur->next->pred = &cur->next;
        !           753:                        cur->pred = last;
        !           754:                        *last = cur;
        !           755:                        freespace->num_entries++;
        !           756: 
        !           757:                        /*
        !           758:                         * Insert this entry into the hint
        !           759:                         * table.
        !           760:                         */
        !           761:                        zone_free_space_hint_insert(freespace, cur);
        !           762:                }
        !           763:        }
        !           764:        else
        !           765:        if (((vm_offset_t)cur + cur->length) == new_space) {
        !           766:                struct zone_free_space_entry    *new;
        !           767: 
        !           768:                /*
        !           769:                 * Delete the existing entry from the
        !           770:                 * hint table.  It is very likely that
        !           771:                 * the hash address will be changing
        !           772:                 * anyways.
        !           773:                 */
        !           774:                zone_free_space_hint_delete(freespace, cur);
        !           775: 
        !           776:                /*
        !           777:                 * Combine the new region with an existing
        !           778:                 * entry, and take the new element from the
        !           779:                 * front of the aggregate region.  Create a
        !           780:                 * new entry for the remainder, and insert it
        !           781:                 * in place of the existing entry.
        !           782:                 */
        !           783:                new_space = (vm_offset_t)cur;
        !           784:                (vm_offset_t)new = (vm_offset_t)cur + size;
        !           785:                new->length = cur->length + space_to_add - size;
        !           786:                if (new->next = cur->next)
        !           787:                        new->next->pred = &new->next;
        !           788:                new->pred = last;
        !           789:                *last = new;
        !           790: 
        !           791:                /*
        !           792:                 * Insert this entry into the hint
        !           793:                 * table.
        !           794:                 */
        !           795:                zone_free_space_hint_insert(freespace, new);
        !           796:        }
        !           797:        
        !           798:        return (new_space);
        !           799: }
        !           800: 
        !           801: #if    0
        !           802: /* NOT USED and OUTDATED */
        !           803: /*
        !           804:  * Ensure that no portion of the specified region
        !           805:  * is represented on the free list (either wholly
        !           806:  * or in part).
        !           807:  */
        !           808: void zone_free_space_remove(freespace, address, size)
        !           809:        struct zone_free_space *freespace;
        !           810:        vm_offset_t address;
        !           811:        vm_size_t size;
        !           812: {
        !           813:        struct zone_free_space_entry
        !           814:                        *cur, **last;
        !           815: 
        !           816:        if (freespace == 0)
        !           817:                freespace = zone_default_space;
        !           818: 
        !           819:        /*
        !           820:         * Search the free list, looking for
        !           821:         * the first suitable entry.
        !           822:         */
        !           823:        last = &freespace->entries;
        !           824:        while ((cur = *last) != 0) {
        !           825:                if ((vm_offset_t)cur >= address) {
        !           826:                        /*
        !           827:                         * Entry is above (and does not
        !           828:                         * overlap) the region. (skip)
        !           829:                         */
        !           830:                        if ((vm_offset_t)cur >= (address + size))
        !           831:                                last = &cur->next;
        !           832:                        else {
        !           833:                                /*
        !           834:                                 * Entry is entirely contained
        !           835:                                 * within the region. (remove)
        !           836:                                 */
        !           837:                                if (((vm_offset_t)cur + cur->length) <=
        !           838:                                                        (address + size)) {
        !           839:                                        *last = cur->next;
        !           840:                                        freespace->num_entries--;
        !           841:                                }
        !           842:                                else {
        !           843:                                        struct zone_free_space_entry    *new;
        !           844: 
        !           845:                                        /*
        !           846:                                         * Entry overlaps the end
        !           847:                                         * of the region. (clip)
        !           848:                                         */
        !           849:                                        (vm_offset_t)new = address + size;
        !           850:                                        new->length = cur->length - 
        !           851:                                                        ((vm_offset_t)new -
        !           852:                                                         (vm_offset_t)cur);
        !           853:                                        new->next = cur->next;
        !           854:                                        *last = new;
        !           855:                                }
        !           856: 
        !           857:                                break;
        !           858:                        }
        !           859:                }
        !           860:                else {
        !           861:                        /*
        !           862:                         * Entry is entirely below the
        !           863:                         * region. (skip)
        !           864:                         */
        !           865:                        if (((vm_offset_t)cur + cur->length) <= address)
        !           866:                                last = &cur->next;
        !           867:                        else {
        !           868:                                /*
        !           869:                                 * Entry overlaps the front
        !           870:                                 * of the region. (clip)
        !           871:                                 */
        !           872:                                cur->length = address - (vm_offset_t)cur;
        !           873:                                break;
        !           874:                        }
        !           875:                }
        !           876:        }
        !           877: }
        !           878: #endif
        !           879: 
        !           880: /*
        !           881:  * Return the elements on the zone free list back
        !           882:  * to the free space pool, coalescing with existing
        !           883:  * space where possible.  Caller must hold the
        !           884:  * zget_space_lock, as well as the lock on the zone.
        !           885:  */
        !           886: void zone_collect(zone)
        !           887:        struct zone     *zone;
        !           888: {
        !           889:        struct zone_free_space_entry    *cur, **last, *new;
        !           890:        vm_offset_t                     *free, *elem, next;
        !           891:        vm_size_t                       elem_size = zone->elem_size;
        !           892:        struct zone_free_space          *freespace = zone->free_space;
        !           893: 
        !           894:        if (!zone_collectable(zone))
        !           895:                return;
        !           896: 
        !           897:        last = &freespace->entries;
        !           898: 
        !           899:        free = &zone->free_elements;
        !           900:        while (((vm_offset_t)elem = *free) != 0) {
        !           901:                zone->cur_size -= elem_size;
        !           902:                next = *elem;
        !           903:                
        !           904:                while ((cur = *last) != 0 &&
        !           905:                                ((vm_offset_t)cur +
        !           906:                                        cur->length) < (vm_offset_t)elem)
        !           907:                        last = &cur->next;
        !           908:                /*
        !           909:                 * Either at end of (maybe empty)
        !           910:                 * list, or new entry before current
        !           911:                 * entry.
        !           912:                 */
        !           913:                if (cur == 0 || ((vm_offset_t)elem + elem_size) <
        !           914:                                                        (vm_offset_t)cur) {
        !           915:                        (vm_offset_t)new = (vm_offset_t)elem;
        !           916:                        new->length = elem_size;
        !           917:                        if (new->next = cur)
        !           918:                                cur->pred = &new->next;
        !           919:                        new->pred = last;
        !           920:                        *last = new;
        !           921:                        freespace->num_entries++;
        !           922: 
        !           923:                        /*
        !           924:                         * Insert this entry into the hint
        !           925:                         * table.
        !           926:                         */
        !           927:                        zone_free_space_hint_insert(freespace, new);
        !           928:                }
        !           929:                else
        !           930:                /*
        !           931:                 * Prepend element to current entry
        !           932:                 */
        !           933:                if (((vm_offset_t)elem + elem_size) == (vm_offset_t)cur) {
        !           934:                        vm_size_t               old_length = cur->length;
        !           935: 
        !           936:                        (vm_offset_t)new = (vm_offset_t)elem;
        !           937:                        new->length = cur->length + elem_size;
        !           938:                        if (new->next = cur->next)
        !           939:                                new->next->pred = &new->next;
        !           940:                        new->pred = last;
        !           941:                        *last = new;
        !           942: 
        !           943:                        /*
        !           944:                         * Update the hint table.
        !           945:                         */
        !           946:                        zone_free_space_hint_prepend(freespace,
        !           947:                                                        new, old_length, cur);
        !           948:                }
        !           949:                else
        !           950:                /*
        !           951:                 * Append element to current entry.
        !           952:                 */
        !           953:                if (((vm_offset_t)cur + cur->length) == (vm_offset_t)elem) {
        !           954:                        vm_size_t               old_length = cur->length;
        !           955: 
        !           956:                        cur->length += elem_size;
        !           957:                        /*
        !           958:                         * Coalesce the current entry with the
        !           959:                         * following one if we are filling the
        !           960:                         * gap between them.
        !           961:                         */
        !           962:                        if (((vm_offset_t)cur + cur->length) ==
        !           963:                                                (vm_offset_t)cur->next) {
        !           964: 
        !           965:                                /*
        !           966:                                 * Delete the obsolete entry
        !           967:                                 * from the hint table.
        !           968:                                 */
        !           969:                                zone_free_space_hint_delete(
        !           970:                                                        freespace, cur->next);
        !           971: 
        !           972:                                cur->length += cur->next->length;
        !           973:                                if (cur->next = cur->next->next)
        !           974:                                        cur->next->pred = &cur->next;
        !           975:                                freespace->num_entries--;
        !           976:                        }
        !           977: 
        !           978:                        /*
        !           979:                         * Update the hint table.
        !           980:                         */
        !           981:                        zone_free_space_hint_append(freespace,
        !           982:                                                        cur, old_length);
        !           983:                }
        !           984:                else
        !           985:                /* WTF?? */;
        !           986:                
        !           987:                *free = next;
        !           988:        }
        !           989:        
        !           990:        zone->last_insert = 0;
        !           991: }
        !           992: 
        !           993: /*
        !           994:  * Scan the collectable free space free lists
        !           995:  * and gather up pages which can be returned to
        !           996:  * the system.  Caller must hold the zget_space_lock.
        !           997:  */
        !           998: struct zone_free_space_entry *
        !           999: zone_free_space_reclaim(void)
        !          1000: {
        !          1001:        struct zone_free_space_entry    **last, *cur, *pages = 0;
        !          1002:        struct zone_free_space          **f = &zone_free_space[0];
        !          1003:        int                             i;
        !          1004: 
        !          1005:        for (i = 1; i < zone_free_space_count; i++) {
        !          1006:                last = &(*++f)->entries;
        !          1007:                while ((cur = *last) != 0) {
        !          1008:                        if (cur->length >= PAGE_SIZE) {
        !          1009:                            vm_offset_t         start, end;
        !          1010:                    
        !          1011:                            start = round_page((vm_offset_t)cur);
        !          1012:                            end = trunc_page(
        !          1013:                                    (vm_offset_t)cur + cur->length);
        !          1014:                            if (start < end &&
        !          1015:                                        start >= zone_min &&
        !          1016:                                        end <= zone_max) {
        !          1017:                                struct zone_free_space_entry    *tmp;
        !          1018: 
        !          1019:                                /*
        !          1020:                                 * Delete this entry from the hint
        !          1021:                                 * table.  Space which is leftover
        !          1022:                                 * after clipping will be added back
        !          1023:                                 * normally after the entries are
        !          1024:                                 * created.
        !          1025:                                 */ 
        !          1026:                                zone_free_space_hint_delete(*f, cur);
        !          1027: 
        !          1028:                                /*
        !          1029:                                 * If the region does not end on a
        !          1030:                                 * page boundary, create a new
        !          1031:                                 * trailing entry.
        !          1032:                                 */
        !          1033:                                if (((vm_offset_t)cur + cur->length) != end) {
        !          1034:                                        (vm_offset_t)tmp = end;
        !          1035:                                        tmp->length = (vm_offset_t)cur +
        !          1036:                                                        cur->length - end;
        !          1037:                                        if (tmp->next = cur->next)
        !          1038:                                                tmp->next->pred = &tmp->next;
        !          1039: 
        !          1040:                                        /*
        !          1041:                                         * Now, if the region does begin
        !          1042:                                         * on a page boundary, just remove
        !          1043:                                         * the current entry.
        !          1044:                                         */
        !          1045:                                        if ((vm_offset_t)cur == start) {
        !          1046:                                                *last = tmp;
        !          1047:                                                tmp->pred = last;
        !          1048:                                        }
        !          1049:                                        /*
        !          1050:                                         * Otherwise, adjust the current
        !          1051:                                         * entry, and link it to the new
        !          1052:                                         * one.  Do not forget to account
        !          1053:                                         * for the new entry.
        !          1054:                                         */
        !          1055:                                        else {
        !          1056:                                                cur->length = start -
        !          1057:                                                        (vm_offset_t)cur;
        !          1058:                                                cur->next = tmp;
        !          1059:                                                tmp->pred = &cur->next;
        !          1060:                                                (*f)->num_entries++;
        !          1061: 
        !          1062:                                                /*
        !          1063:                                                 * Reinsert the leading
        !          1064:                                                 * entry into the hint
        !          1065:                                                 * table.
        !          1066:                                                 */
        !          1067:                                                zone_free_space_hint_insert(
        !          1068:                                                                *f, cur);
        !          1069:                                        }
        !          1070: 
        !          1071:                                        /*
        !          1072:                                         * Insert the new trailing entry
        !          1073:                                         * into the hint table.
        !          1074:                                         */
        !          1075:                                        zone_free_space_hint_insert(*f, tmp);
        !          1076:                                }
        !          1077:                                /*
        !          1078:                                 * If the region does not begin on a
        !          1079:                                 * page boundary (but the end does),
        !          1080:                                 * adjust the current entry.
        !          1081:                                 */
        !          1082:                                else if ((vm_offset_t)cur != start) {
        !          1083:                                        cur->length = start - (vm_offset_t)cur;
        !          1084: 
        !          1085:                                        /*
        !          1086:                                         * Reinsert the entry into
        !          1087:                                         * the hint table.
        !          1088:                                         */
        !          1089:                                        zone_free_space_hint_insert(*f, cur);
        !          1090:                                }
        !          1091:                                /*
        !          1092:                                 * If no clipping is required, just
        !          1093:                                 * remove the current entry.
        !          1094:                                 */
        !          1095:                                else {
        !          1096:                                        if (*last = cur->next)
        !          1097:                                                cur->next->pred = last;
        !          1098:                                        (*f)->num_entries--;
        !          1099:                                }
        !          1100: 
        !          1101:                                /*
        !          1102:                                 * Add the new page aligned region
        !          1103:                                 * to the list of pages to be freed.
        !          1104:                                 * Continue on with the next entry.
        !          1105:                                 */
        !          1106:                                (vm_offset_t)tmp = start;
        !          1107:                                tmp->length = end - start;
        !          1108:                                tmp->next = pages;
        !          1109:                                pages = tmp;
        !          1110:                                continue;
        !          1111:                            }
        !          1112:                        }
        !          1113: 
        !          1114:                        /*
        !          1115:                         * Skip this entry.
        !          1116:                         */
        !          1117:                        last = &cur->next;
        !          1118:                }
        !          1119:        }
        !          1120: 
        !          1121:        return (pages);
        !          1122: }
        !          1123: 
        !          1124: /*
        !          1125:  * Contiguous space allocator for non-paged zones. Allocates "size" amount
        !          1126:  * of memory from zone_map.
        !          1127:  */
        !          1128: 
        !          1129: vm_offset_t zget_space(freespace, size, canblock)
        !          1130:        struct zone_free_space *freespace;
        !          1131:        vm_size_t size;
        !          1132:        boolean_t canblock;
        !          1133: {
        !          1134:        vm_offset_t     new_space = 0;
        !          1135:        vm_offset_t     result;
        !          1136:        vm_size_t       space_to_add;
        !          1137:        struct zone_free_space_entry
        !          1138:                        *cur, **last;
        !          1139: 
        !          1140:        if (freespace == 0)
        !          1141:                freespace = zone_default_space;
        !          1142: 
        !          1143:        /*
        !          1144:         * Round up all requests (even 0) to
        !          1145:         * our minimum allocation unit.
        !          1146:         */
        !          1147:        if (size > ZONE_MIN_ALLOC)
        !          1148:                size = ((size + (ZONE_MIN_ALLOC - 1)) & ~(ZONE_MIN_ALLOC - 1));
        !          1149:        else
        !          1150:                size = ZONE_MIN_ALLOC;
        !          1151: 
        !          1152:        simple_lock(simple_lock_addr(zget_space_lock));
        !          1153:        for (;;) {
        !          1154:                if ((cur = zone_free_space_lookup(freespace, size)) != 0) {
        !          1155:                        last = cur->pred;
        !          1156: 
        !          1157:                        /*
        !          1158:                         * The entry which was found has been
        !          1159:                         * removed from the hint table, but
        !          1160:                         * remains in the free list.  Trim off
        !          1161:                         * the space to be returned.
        !          1162:                         */
        !          1163:                        if ((cur->length - size) < ZONE_MIN_ALLOC) {
        !          1164:                                /*
        !          1165:                                 * This is a real lose if it
        !          1166:                                 * happens in a collectable
        !          1167:                                 * space, since the memory
        !          1168:                                 * will be lost, making it
        !          1169:                                 * impossible to reclaim the
        !          1170:                                 * page later.
        !          1171:                                 */
        !          1172:                                if (*last = cur->next)
        !          1173:                                        cur->next->pred = last;
        !          1174:                                freespace->num_entries--;
        !          1175:                        }
        !          1176:                        else {
        !          1177:                                struct zone_free_space_entry    *new;
        !          1178: 
        !          1179:                                /*
        !          1180:                                 * Create a new entry for the
        !          1181:                                 * remaining space and position
        !          1182:                                 * on the free list.
        !          1183:                                 */
        !          1184:                                (vm_offset_t)new = (vm_offset_t)cur + size;
        !          1185:                                new->length = cur->length - size;
        !          1186:                                if (new->next = cur->next)
        !          1187:                                        new->next->pred = &new->next;
        !          1188:                                new->pred = last;
        !          1189:                                *last = new;
        !          1190: 
        !          1191:                                /*
        !          1192:                                 * After trimming the entry, reinsert
        !          1193:                                 * it back into the hint table.
        !          1194:                                 */
        !          1195:                                zone_free_space_hint_insert(freespace, new);
        !          1196:                        }
        !          1197:                        result = (vm_offset_t)cur;
        !          1198:                        break;
        !          1199:                }
        !          1200:                else if (new_space == 0) {
        !          1201:                        /*
        !          1202:                         *      Add at least one page to allocation area.
        !          1203:                         */
        !          1204:        
        !          1205:                        space_to_add = round_page(size);
        !          1206: 
        !          1207:                        if (zdata_size >= space_to_add) {
        !          1208:                                zdata_size -= space_to_add;
        !          1209:                                result = zone_free_space_add(
        !          1210:                                                        freespace,
        !          1211:                                                        size,
        !          1212:                                                        zdata + zdata_size,
        !          1213:                                                        space_to_add);
        !          1214:                                break;
        !          1215:                        }
        !          1216: 
        !          1217:                        /*
        !          1218:                         *      Memory cannot be wired down while holding
        !          1219:                         *      any locks that the pageout daemon might
        !          1220:                         *      need to free up pages.  [Making the zget_space
        !          1221:                         *      lock a complex lock does not help in this
        !          1222:                         *      regard.]
        !          1223:                         *
        !          1224:                         *      Unlock and allocate memory.  Because several
        !          1225:                         *      threads might try to do this at once, don't
        !          1226:                         *      use the memory before checking for available
        !          1227:                         *      space again.
        !          1228:                         */
        !          1229: 
        !          1230:                        simple_unlock(simple_lock_addr(zget_space_lock));
        !          1231:                        {
        !          1232:                                kern_return_t   kr;
        !          1233: 
        !          1234:                                kr = kmem_alloc_zone(zone_map,
        !          1235:                                                     &new_space, space_to_add,
        !          1236:                                                        canblock);
        !          1237:                                if (kr != KERN_SUCCESS) {
        !          1238:                                        if (kr == KERN_NO_SPACE)
        !          1239:                                                panic("zget_space");
        !          1240: 
        !          1241:                                        return(0);
        !          1242:                                }
        !          1243:                        }
        !          1244: 
        !          1245:                        simple_lock(simple_lock_addr(zget_space_lock));
        !          1246:                        continue;
        !          1247:                }
        !          1248:                else {
        !          1249:                        /*
        !          1250:                         *      Memory was allocated in a previous iteration.
        !          1251:                         */
        !          1252: 
        !          1253:                        result = zone_free_space_add(
        !          1254:                                                freespace,
        !          1255:                                                size,
        !          1256:                                                new_space,
        !          1257:                                                space_to_add);
        !          1258:                        new_space = 0;
        !          1259:                        break;
        !          1260:                }
        !          1261:        }
        !          1262:        simple_unlock(simple_lock_addr(zget_space_lock));
        !          1263: 
        !          1264:        if (new_space != 0)
        !          1265:                kmem_free(zone_map, new_space, space_to_add);
        !          1266: 
        !          1267:        return(result);
        !          1268: }
        !          1269: 
        !          1270: static
        !          1271: struct zone_free_space *
        !          1272: zone_free_space_alloc(alloc_unit, alloc_max)
        !          1273:        vm_size_t       alloc_unit;
        !          1274:        vm_size_t       alloc_max;
        !          1275: {
        !          1276:        struct zone_free_space  *freespace, **f;
        !          1277:        
        !          1278:        if (zone_free_space_count >=
        !          1279:                        (sizeof (zone_free_space) / sizeof (freespace)))
        !          1280:                return (0);
        !          1281:        
        !          1282:        f = &zone_free_space[zone_free_space_count++];
        !          1283: 
        !          1284:        (vm_offset_t)freespace = zget_space(
        !          1285:                                        zone_default_space,
        !          1286:                                        sizeof (struct zone_free_space), 
        !          1287:                                        FALSE);
        !          1288:        freespace->alloc_unit = alloc_unit;
        !          1289:        freespace->alloc_max = alloc_max;
        !          1290: 
        !          1291:        freespace->entries = 0;
        !          1292:        freespace->num_entries = 0;
        !          1293:        
        !          1294:        freespace->hash_shift = 0;
        !          1295:        while (!(alloc_unit & 01)) {
        !          1296:                freespace->hash_shift++; alloc_unit >>= 1;
        !          1297:        }
        !          1298: 
        !          1299:        freespace->num_hints = freespace->alloc_max >> freespace->hash_shift;
        !          1300:        (vm_offset_t)freespace->hints =
        !          1301:                        zget_space(
        !          1302:                                zone_default_space,
        !          1303:                                freespace->num_hints *
        !          1304:                                        sizeof (struct zone_free_space_hint),
        !          1305:                                FALSE);
        !          1306:        bzero(freespace->hints, freespace->num_hints *
        !          1307:                                        sizeof (struct zone_free_space_hint));
        !          1308: 
        !          1309:        *f = freespace;
        !          1310:        
        !          1311:        return (freespace);
        !          1312: }
        !          1313: 
        !          1314: static
        !          1315: void
        !          1316: zone_free_space_select(zone)
        !          1317:        zone_t          zone;
        !          1318: {
        !          1319:        struct zone_free_space  **f = &zone_free_space[1];
        !          1320:        vm_size_t       elem_size;
        !          1321:        int             i;
        !          1322:        
        !          1323:        if (zone->cur_size > 0)
        !          1324:                return;
        !          1325:        
        !          1326:        for (i = 1; i < zone_free_space_count; i++) {
        !          1327:                elem_size = ((zone->elem_size + ((*f)->alloc_unit - 1))
        !          1328:                                & ~((*f)->alloc_unit - 1));
        !          1329:                if (elem_size <= (*f)->alloc_max) {
        !          1330:                        zone->elem_size = elem_size;                            
        !          1331:                        zone->free_space = *f;
        !          1332:                        break;
        !          1333:                }
        !          1334:                
        !          1335:                f++;
        !          1336:        }
        !          1337: }
        !          1338: 
        !          1339: /*
        !          1340:  *     Initialize the "zone of zones" which uses fixed memory allocated
        !          1341:  *     earlier in memory initialization.  zone_bootstrap is called
        !          1342:  *     before zone_init.
        !          1343:  */
        !          1344: void zone_bootstrap(void)
        !          1345: {
        !          1346:        simple_lock_init(simple_lock_addr(all_zones_lock));
        !          1347:        first_zone = ZONE_NULL;
        !          1348:        last_zone = &first_zone;
        !          1349:        num_zones = 0;
        !          1350: 
        !          1351:        if (sizeof (struct zone_free_space_entry) > ZONE_MIN_ALLOC)
        !          1352:                panic("zone_bootstrap");
        !          1353: 
        !          1354:        simple_lock_init(simple_lock_addr(zget_space_lock));
        !          1355: 
        !          1356:        _zone_default_space.hints = &_zone_default_space_hint;
        !          1357:        _zone_default_space.num_hints = 1;
        !          1358:        
        !          1359:        zone_free_space[0] = &_zone_default_space;
        !          1360:        zone_free_space_count = 1;
        !          1361: 
        !          1362:        zone_zone = ZONE_NULL;
        !          1363:        zone_zone = zinit(sizeof(struct zone), 128 * sizeof(struct zone),
        !          1364:                          sizeof(struct zone), FALSE, "zones");
        !          1365: 
        !          1366:        zone_free_space_alloc(16,       96);
        !          1367:        zone_free_space_alloc(128,      768);
        !          1368:        zone_free_space_alloc(1024,     PAGE_SIZE);
        !          1369: }
        !          1370: 
        !          1371: vm_size_t
        !          1372: zone_map_sizer(void)
        !          1373: {
        !          1374: #if defined(__ppc__)
        !          1375:        vm_size_t       map_size = mem_size / 4;
        !          1376: #else
        !          1377:        vm_size_t       map_size = mem_size / 8;
        !          1378: #endif
        !          1379: 
        !          1380:        if (map_size < zone_map_size_min)
        !          1381:                map_size = zone_map_size_min;
        !          1382:        else
        !          1383:        if (map_size > zone_map_size_max)
        !          1384:                map_size = zone_map_size_max;
        !          1385: 
        !          1386:        return (map_size);
        !          1387: }
        !          1388: 
        !          1389: void zone_init(void)
        !          1390: {
        !          1391:        zone_map_size = zone_map_sizer();
        !          1392: 
        !          1393:        zone_map = kmem_suballoc(kernel_map, &zone_min, &zone_max,
        !          1394:                                 zone_map_size, FALSE);
        !          1395: }
        !          1396: 
        !          1397: 
        !          1398: /*
        !          1399:  *     zalloc returns an element from the specified zone.
        !          1400:  */
        !          1401: static
        !          1402: vm_offset_t zalloc_canblock(zone, canblock)
        !          1403:        register zone_t zone;
        !          1404:        boolean_t canblock;
        !          1405: {
        !          1406:        vm_offset_t     addr;
        !          1407: 
        !          1408:        if (zone == ZONE_NULL)
        !          1409:                panic ("zalloc: null zone");
        !          1410: 
        !          1411:        lock_zone(zone);
        !          1412:        REMOVE_FROM_ZONE(zone, addr, vm_offset_t);
        !          1413:        while (addr == 0) {
        !          1414:                /*
        !          1415:                 *      If nothing was there, try to get more
        !          1416:                 */
        !          1417:                if (zone->doing_alloc) {
        !          1418:                        /*
        !          1419:                         *      Someone is allocating memory for this zone.
        !          1420:                         *      Wait for it to show up, then try again.
        !          1421:                         */
        !          1422:                        if (!canblock) {
        !          1423:                                unlock_zone(zone);
        !          1424:                                return(0);
        !          1425:                        }
        !          1426:                        assert_wait((event_t)&zone->doing_alloc, TRUE);
        !          1427:                        /* XXX say wakeup needed */
        !          1428:                        unlock_zone(zone);
        !          1429:                        thread_block_with_continuation((void (*)()) 0);
        !          1430:                        lock_zone(zone);
        !          1431:                }
        !          1432:                else {
        !          1433:                        if ((zone->cur_size + (zone->pageable ?
        !          1434:                                zone->alloc_size : zone->elem_size)) >
        !          1435:                            zone->max_size) {
        !          1436:                                if (zone->exhaustible)
        !          1437:                                        break;
        !          1438: 
        !          1439:                                if (zone->expandable) {
        !          1440:                                        /*
        !          1441:                                         * We're willing to overflow certain
        !          1442:                                         * zones, but not without complaining.
        !          1443:                                         *
        !          1444:                                         * This is best used in conjunction
        !          1445:                                         * with the collecatable flag. What we
        !          1446:                                         * want is an assurance we can get the
        !          1447:                                         * memory back, assuming there's no
        !          1448:                                         * leak. 
        !          1449:                                         */
        !          1450:                                        zone->max_size += (zone->max_size >> 1);
        !          1451:                                } else if (!zone_ignore_overflow) {
        !          1452:                                        unlock_zone(zone);
        !          1453:                                        if (!canblock)
        !          1454:                                                return(0);
        !          1455:                                        printf("zone \"%s\" empty.\n",
        !          1456:                                                zone->zone_name);
        !          1457:                                        panic("zalloc");
        !          1458:                                }
        !          1459:                        }
        !          1460: 
        !          1461:                        if (zone->pageable)
        !          1462:                                zone->doing_alloc = TRUE;
        !          1463:                        unlock_zone(zone);
        !          1464: 
        !          1465:                        if (zone->pageable) {
        !          1466:                                if (kmem_alloc_pageable(zone_map, &addr,
        !          1467:                                                        zone->alloc_size)
        !          1468:                                                        != KERN_SUCCESS)
        !          1469:                                        panic("zalloc");
        !          1470:                                zcram(zone, addr, zone->alloc_size);
        !          1471:                                lock_zone(zone);
        !          1472:                                zone->doing_alloc = FALSE; 
        !          1473:                                /* XXX check before doing this */
        !          1474:                                thread_wakeup((event_t)&zone->doing_alloc);
        !          1475: 
        !          1476:                                REMOVE_FROM_ZONE(zone, addr, vm_offset_t);
        !          1477:                        } else {
        !          1478:                                addr = zget_space(
        !          1479:                                        zone->free_space,
        !          1480:                                        zone->elem_size,
        !          1481:                                        canblock);
        !          1482:                                if (addr == 0) {
        !          1483:                                        if (!canblock)
        !          1484:                                                return(0);
        !          1485:                                        panic("zalloc");
        !          1486:                                }
        !          1487: 
        !          1488:                                lock_zone(zone);
        !          1489:                                zone->count++;
        !          1490:                                zone->cur_size += zone->elem_size;
        !          1491:                                unlock_zone(zone);
        !          1492:                                return(addr);
        !          1493:                        }
        !          1494:                }
        !          1495:        }
        !          1496: 
        !          1497:        unlock_zone(zone);
        !          1498:        return(addr);
        !          1499: }
        !          1500: 
        !          1501: vm_offset_t zalloc(zone)
        !          1502:        register zone_t zone;
        !          1503: {
        !          1504:        return (zalloc_canblock(zone, TRUE));
        !          1505: }
        !          1506: 
        !          1507: vm_offset_t zalloc_noblock(zone)
        !          1508:        register zone_t zone;
        !          1509: {
        !          1510:        return (zalloc_canblock(zone, FALSE));
        !          1511: }
        !          1512: 
        !          1513: 
        !          1514: /*
        !          1515:  *     zget returns an element from the specified zone
        !          1516:  *     and immediately returns nothing if there is nothing there.
        !          1517:  *
        !          1518:  *     This form should be used when you can not block (like when
        !          1519:  *     processing an interrupt).
        !          1520:  */
        !          1521: vm_offset_t zget(zone)
        !          1522:        register zone_t zone;
        !          1523: {
        !          1524:        register vm_offset_t    addr;
        !          1525: 
        !          1526:        if (zone == ZONE_NULL)
        !          1527:                panic ("zalloc: null zone");
        !          1528: 
        !          1529:        lock_zone(zone);
        !          1530:        REMOVE_FROM_ZONE(zone, addr, vm_offset_t);
        !          1531:        unlock_zone(zone);
        !          1532: 
        !          1533:        return(addr);
        !          1534: }
        !          1535: 
        !          1536: boolean_t zone_check = FALSE;
        !          1537: 
        !          1538: void zfree(zone, elem)
        !          1539:        register zone_t zone;
        !          1540:        vm_offset_t     elem;
        !          1541: {
        !          1542:        lock_zone(zone);
        !          1543:        if (zone_check) {
        !          1544:                vm_offset_t this;
        !          1545: 
        !          1546:                /* check the zone's consistency */
        !          1547: 
        !          1548:                for (this = zone->free_elements;
        !          1549:                     this != 0;
        !          1550:                     this = * (vm_offset_t *) this)
        !          1551:                        if (this == elem)
        !          1552:                                panic("zfree");
        !          1553:        }
        !          1554:        ADD_TO_ZONE(zone, elem);
        !          1555:        unlock_zone(zone);
        !          1556: }
        !          1557: 
        !          1558: void zcollectable(zone) 
        !          1559:        zone_t          zone;
        !          1560: {
        !          1561:        /* zones are collectable by default
        !          1562:         * and cannot later be changed back to collectable */
        !          1563: }
        !          1564: 
        !          1565: void zchange(zone, pageable, sleepable, exhaustible, collectable)
        !          1566:        zone_t          zone;
        !          1567:        boolean_t       pageable;
        !          1568:        boolean_t       sleepable;
        !          1569:        boolean_t       exhaustible;
        !          1570:        boolean_t       collectable;
        !          1571: {
        !          1572:        zone->pageable = pageable;
        !          1573:        zone->sleepable = sleepable;
        !          1574:        zone->exhaustible = exhaustible;
        !          1575:        /* zones are collectable by default
        !          1576:         * and later can only be changed to non-collectable */
        !          1577:        if (!collectable)
        !          1578:                zone->free_space = zone_default_space;
        !          1579:        lock_zone_init(zone);
        !          1580: }
        !          1581: 
        !          1582: #if    MACH_DEBUG
        !          1583: kern_return_t host_zone_info(host, namesp, namesCntp, infop, infoCntp)
        !          1584:        host_t          host;
        !          1585:        zone_name_array_t *namesp;
        !          1586:        unsigned int    *namesCntp;
        !          1587:        zone_info_array_t *infop;
        !          1588:        unsigned int    *infoCntp;
        !          1589: {
        !          1590:        zone_name_t     *names;
        !          1591:        vm_offset_t     names_addr;
        !          1592:        vm_size_t       names_size = 0; /*'=0' to quiet gcc warnings */
        !          1593:        zone_info_t     *info;
        !          1594:        vm_offset_t     info_addr;
        !          1595:        vm_size_t       info_size = 0; /*'=0' to quiet gcc warnings */
        !          1596:        unsigned int    max_zones, i;
        !          1597:        zone_t          z;
        !          1598:        kern_return_t   kr;
        !          1599: 
        !          1600:        if (host == HOST_NULL)
        !          1601:                return KERN_INVALID_HOST;
        !          1602: 
        !          1603:        /*
        !          1604:         *      We assume that zones aren't freed once allocated.
        !          1605:         *      We won't pick up any zones that are allocated later.
        !          1606:         */
        !          1607: 
        !          1608:        simple_lock(simple_lock_addr(all_zones_lock));
        !          1609:        max_zones = num_zones;
        !          1610:        z = first_zone;
        !          1611:        simple_unlock(simple_lock_addr(all_zones_lock));
        !          1612: 
        !          1613:        if (max_zones <= *namesCntp) {
        !          1614:                /* use in-line memory */
        !          1615: 
        !          1616:                names = *namesp;
        !          1617:        } else {
        !          1618:                names_size = round_page(max_zones * sizeof *names);
        !          1619:                kr = kmem_alloc_pageable(ipc_kernel_map,
        !          1620:                                         &names_addr, names_size);
        !          1621:                if (kr != KERN_SUCCESS)
        !          1622:                        return kr;
        !          1623: 
        !          1624:                names = (zone_name_t *) names_addr;
        !          1625:        }
        !          1626: 
        !          1627:        if (max_zones <= *infoCntp) {
        !          1628:                /* use in-line memory */
        !          1629: 
        !          1630:                info = *infop;
        !          1631:        } else {
        !          1632:                info_size = round_page(max_zones * sizeof *info);
        !          1633:                kr = kmem_alloc_pageable(ipc_kernel_map,
        !          1634:                                         &info_addr, info_size);
        !          1635:                if (kr != KERN_SUCCESS) {
        !          1636:                        if (names != *namesp)
        !          1637:                                kmem_free(ipc_kernel_map,
        !          1638:                                          names_addr, names_size);
        !          1639:                        return kr;
        !          1640:                }
        !          1641: 
        !          1642:                info = (zone_info_t *) info_addr;
        !          1643:        }
        !          1644: 
        !          1645:        for (i = 0; i < max_zones; i++) {
        !          1646:                zone_name_t *zn = &names[i];
        !          1647:                zone_info_t *zi = &info[i];
        !          1648:                struct zone zcopy;
        !          1649: 
        !          1650:                assert(z != ZONE_NULL);
        !          1651: 
        !          1652:                lock_zone(z);
        !          1653:                zcopy = *z;
        !          1654:                unlock_zone(z);
        !          1655: 
        !          1656:                simple_lock(simple_lock_addr(all_zones_lock));
        !          1657:                z = z->next_zone;
        !          1658:                simple_unlock(simple_lock_addr(all_zones_lock));
        !          1659: 
        !          1660:                /* assuming here the name data is static */
        !          1661:                (void) strncpy(zn->zn_name, zcopy.zone_name,
        !          1662:                               sizeof zn->zn_name);
        !          1663: 
        !          1664:                zi->zi_count = zcopy.count;
        !          1665:                zi->zi_cur_size = zcopy.cur_size;
        !          1666:                zi->zi_max_size = zcopy.max_size;
        !          1667:                zi->zi_elem_size = zcopy.elem_size;
        !          1668:                zi->zi_alloc_size = zcopy.alloc_size;
        !          1669:                zi->zi_pageable = zcopy.pageable;
        !          1670:                zi->zi_sleepable = zcopy.sleepable;
        !          1671:                zi->zi_exhaustible = zcopy.exhaustible;
        !          1672:                zi->zi_collectable = zone_collectable(&zcopy);
        !          1673:        }
        !          1674: 
        !          1675:        if (names != *namesp) {
        !          1676:                vm_size_t used;
        !          1677: #if    MACH_OLD_VM_COPY
        !          1678: #else
        !          1679:                vm_map_copy_t copy;
        !          1680: #endif
        !          1681: 
        !          1682:                used = max_zones * sizeof *names;
        !          1683: 
        !          1684:                if (used != names_size)
        !          1685:                        bzero((char *) (names_addr + used), names_size - used);
        !          1686: 
        !          1687: #if    MACH_OLD_VM_COPY
        !          1688:                kr = vm_move(
        !          1689:                        ipc_kernel_map, names_addr,
        !          1690:                        ipc_soft_map, names_size,
        !          1691:                        TRUE, &names_addr);
        !          1692:                assert(kr == KERN_SUCCESS);
        !          1693: 
        !          1694:                *namesp = (zone_name_t *) names_addr;
        !          1695: #else
        !          1696:                kr = vm_map_copyin(ipc_kernel_map, names_addr, names_size,
        !          1697:                                   TRUE, &copy);
        !          1698:                assert(kr == KERN_SUCCESS);
        !          1699: 
        !          1700:                *namesp = (zone_name_t *) copy;
        !          1701: #endif
        !          1702:        }
        !          1703:        *namesCntp = max_zones;
        !          1704: 
        !          1705:        if (info != *infop) {
        !          1706:                vm_size_t used;
        !          1707: #if    MACH_OLD_VM_COPY
        !          1708: #else
        !          1709:                vm_map_copy_t copy;
        !          1710: #endif
        !          1711: 
        !          1712:                used = max_zones * sizeof *info;
        !          1713: 
        !          1714:                if (used != info_size)
        !          1715:                        bzero((char *) (info_addr + used), info_size - used);
        !          1716: 
        !          1717: #if    MACH_OLD_VM_COPY
        !          1718:                kr = vm_move(
        !          1719:                        ipc_kernel_map, info_addr,
        !          1720:                        ipc_soft_map, info_size,
        !          1721:                        TRUE, &info_addr);
        !          1722:                assert(kr == KERN_SUCCESS);
        !          1723: 
        !          1724:                *infop = (zone_info_t *) info_addr;
        !          1725: #else
        !          1726:                kr = vm_map_copyin(ipc_kernel_map, info_addr, info_size,
        !          1727:                                   TRUE, &copy);
        !          1728:                assert(kr == KERN_SUCCESS);
        !          1729: 
        !          1730:                *infop = (zone_info_t *) copy;
        !          1731: #endif
        !          1732:        }
        !          1733:        *infoCntp = max_zones;
        !          1734: 
        !          1735:        return KERN_SUCCESS;
        !          1736: }
        !          1737: 
        !          1738: kern_return_t host_zone_free_space_info(
        !          1739:                                host,
        !          1740:                                infop, infoCnt,
        !          1741:                                chunksp, chunksCnt)
        !          1742:        host_t                          host;
        !          1743:        zone_free_space_info_array_t    *infop;
        !          1744:        mach_msg_type_number_t          *infoCnt;
        !          1745:        zone_free_space_chunk_array_t   *chunksp;
        !          1746:        mach_msg_type_number_t          *chunksCnt;
        !          1747: {
        !          1748:        kern_return_t   kr;
        !          1749:        vm_size_t       size1, size2;
        !          1750:        vm_offset_t     addr1, addr2;
        !          1751:        vm_offset_t     memory1, memory2;
        !          1752:        mach_msg_type_number_t
        !          1753:                        actual1, actual2;
        !          1754:        zone_free_space_info_t
        !          1755:                        *info;
        !          1756:        zone_free_space_chunk_t
        !          1757:                        *chunk;
        !          1758:        struct zone_free_space_entry
        !          1759:                        **last, *cur;
        !          1760:        struct zone_free_space
        !          1761:                        *freespace;
        !          1762:        int             i;
        !          1763: 
        !          1764:        if (host == HOST_NULL)
        !          1765:                return KERN_INVALID_HOST;
        !          1766: 
        !          1767:        size1 = size2 = 0;
        !          1768: 
        !          1769:        for (;;) {
        !          1770:                vm_size_t       size1_needed, size2_needed;
        !          1771: 
        !          1772:                size1_needed = size2_needed = 0;
        !          1773: 
        !          1774:                simple_lock(simple_lock_addr(zget_space_lock));
        !          1775: 
        !          1776:                actual1 = actual2 = 0;
        !          1777:                
        !          1778:                for (actual1 = 0; actual1 < zone_free_space_count; actual1++)
        !          1779:                        actual2 += zone_free_space[actual1]->num_entries;
        !          1780:                
        !          1781:                if (actual1 > *infoCnt)
        !          1782:                        size1_needed = round_page(
        !          1783:                                actual1 * sizeof (**infop));
        !          1784:                
        !          1785:                if (actual2 > *chunksCnt)
        !          1786:                        size2_needed = round_page(
        !          1787:                                actual2 * sizeof (**chunksp));
        !          1788: 
        !          1789:                if (size1_needed <= size1 &&
        !          1790:                                size2_needed <= size2)
        !          1791:                        break;
        !          1792: 
        !          1793:                simple_unlock(simple_lock_addr(zget_space_lock));
        !          1794: 
        !          1795:                if (size1 < size1_needed) {
        !          1796:                        if (size1 != 0)
        !          1797:                                kmem_free(ipc_kernel_map, addr1, size1);
        !          1798:                        size1 = size1_needed;
        !          1799: 
        !          1800:                        kr = kmem_alloc_pageable(
        !          1801:                                                ipc_kernel_map, &addr1, size1);
        !          1802:                        if (kr != KERN_SUCCESS) {
        !          1803:                                if (size2 != 0)
        !          1804:                                        kmem_free(
        !          1805:                                                ipc_kernel_map, addr2, size2);
        !          1806:                                return KERN_RESOURCE_SHORTAGE;
        !          1807:                        }
        !          1808: #if    MACH_OLD_VM_COPY
        !          1809:                        kr = vm_map_pageable(
        !          1810:                                ipc_kernel_map, addr1, addr1 + size1, FALSE);
        !          1811:                        assert(kr == KERN_SUCCESS);
        !          1812: #else
        !          1813:                        kr = vm_map_pageable(
        !          1814:                                        ipc_kernel_map, addr1, addr1 + size1,
        !          1815:                                                VM_PROT_READ|VM_PROT_WRITE);
        !          1816:                        assert(kr == KERN_SUCCESS);
        !          1817: #endif
        !          1818:                }
        !          1819: 
        !          1820:                if (size2 < size2_needed) {
        !          1821:                        if (size2 != 0)
        !          1822:                                kmem_free(ipc_kernel_map, addr2, size2);
        !          1823:                        size2 = size2_needed;
        !          1824: 
        !          1825:                        kr = kmem_alloc_pageable(
        !          1826:                                                ipc_kernel_map, &addr2, size2);
        !          1827:                        if (kr != KERN_SUCCESS) {
        !          1828:                                if (size1 != 0)
        !          1829:                                        kmem_free(
        !          1830:                                                ipc_kernel_map, addr1, size1);
        !          1831:                                return KERN_RESOURCE_SHORTAGE;
        !          1832:                        }
        !          1833: #if    MACH_OLD_VM_COPY
        !          1834:                        kr = vm_map_pageable(
        !          1835:                                ipc_kernel_map, addr2, addr2 + size2, FALSE);
        !          1836:                        assert(kr == KERN_SUCCESS);
        !          1837: #else
        !          1838:                        kr = vm_map_pageable(
        !          1839:                                        ipc_kernel_map, addr2, addr2 + size2,
        !          1840:                                                VM_PROT_READ|VM_PROT_WRITE);
        !          1841:                        assert(kr == KERN_SUCCESS);
        !          1842: #endif
        !          1843:                }
        !          1844:        }
        !          1845: 
        !          1846:        if (size1 != 0)
        !          1847:                info = (zone_free_space_info_t *)addr1;
        !          1848:        else
        !          1849:                info = *infop;
        !          1850: 
        !          1851:        if (size2 != 0)
        !          1852:                chunk = (zone_free_space_chunk_t *)addr2;
        !          1853:        else
        !          1854:                chunk = *chunksp;
        !          1855: 
        !          1856:        for (i = 0; i < actual1; i++) {
        !          1857:                freespace = zone_free_space[i];
        !          1858: 
        !          1859:                info->zf_alloc_unit = freespace->alloc_unit;
        !          1860:                info->zf_alloc_max = freespace->alloc_max;
        !          1861:                info->zf_num_chunks = freespace->num_entries;
        !          1862:                info++;
        !          1863: 
        !          1864:                last = &freespace->entries;
        !          1865:                while ((cur = *last) != 0) {
        !          1866:                        chunk->zf_address = (vm_offset_t)cur;
        !          1867:                        chunk->zf_length = cur->length;
        !          1868:                        chunk++;
        !          1869:                        
        !          1870:                        last = &cur->next;
        !          1871:                }
        !          1872:        }
        !          1873: 
        !          1874:        simple_unlock(simple_lock_addr(zget_space_lock));
        !          1875: 
        !          1876:        if (actual1 != 0 && size1 != 0) {
        !          1877:                vm_size_t       size_used;
        !          1878:                
        !          1879:                size_used = round_page(actual1 * sizeof (**infop));
        !          1880: 
        !          1881: #if    MACH_OLD_VM_COPY
        !          1882:                kr = vm_map_pageable(
        !          1883:                        ipc_kernel_map, addr1, addr1 + size_used, TRUE);
        !          1884:                assert(kr == KERN_SUCCESS);
        !          1885: 
        !          1886:                kr = vm_move(
        !          1887:                        ipc_kernel_map, addr1,
        !          1888:                        ipc_soft_map, size_used,
        !          1889:                        TRUE, &memory1);
        !          1890:                assert(kr == KERN_SUCCESS);
        !          1891: #else
        !          1892:                kr = vm_map_pageable(
        !          1893:                                ipc_kernel_map,
        !          1894:                                addr1, addr1 + size_used, VM_PROT_NONE);
        !          1895:                assert(kr == KERN_SUCCESS);
        !          1896:        
        !          1897:                kr = vm_map_copyin(
        !          1898:                                ipc_kernel_map, addr1, size_used,
        !          1899:                                TRUE, &memory1);
        !          1900:                assert(kr == KERN_SUCCESS);
        !          1901: #endif
        !          1902:        
        !          1903:                if (size_used != size1)
        !          1904:                        kmem_free(
        !          1905:                                ipc_kernel_map,
        !          1906:                                addr1 + size_used, size1 - size_used);
        !          1907: 
        !          1908:                *infop = (zone_free_space_info_t *)memory1;
        !          1909:        }
        !          1910:        else if (actual1 == 0) {
        !          1911: #if    MACH_OLD_VM_COPY
        !          1912:                *infop = (zone_free_space_info_t *)0;
        !          1913: #else
        !          1914:                *infop = (zone_free_space_info_t *)VM_MAP_COPY_NULL;
        !          1915: #endif
        !          1916: 
        !          1917:                if (size1 != 0)
        !          1918:                        kmem_free(ipc_kernel_map, addr1, size1);
        !          1919:        }
        !          1920:        
        !          1921:        *infoCnt = actual1;
        !          1922: 
        !          1923:        if (actual2 != 0 && size2 != 0) {
        !          1924:                vm_size_t       size_used;
        !          1925: 
        !          1926:                size_used = round_page(actual2 * sizeof (**chunksp));
        !          1927: 
        !          1928: #if    MACH_OLD_VM_COPY
        !          1929:                kr = vm_map_pageable(
        !          1930:                        ipc_kernel_map, addr2, addr2 + size_used, TRUE);
        !          1931:                assert(kr == KERN_SUCCESS);
        !          1932: 
        !          1933:                kr = vm_move(
        !          1934:                        ipc_kernel_map, addr2,
        !          1935:                        ipc_soft_map, size_used,
        !          1936:                        TRUE, &memory2);
        !          1937:                assert(kr == KERN_SUCCESS);
        !          1938: #else
        !          1939:                kr = vm_map_pageable(
        !          1940:                                ipc_kernel_map,
        !          1941:                                addr2, addr2 + size2, VM_PROT_NONE);
        !          1942:                assert(kr == KERN_SUCCESS);
        !          1943: 
        !          1944:                kr = vm_map_copyin(
        !          1945:                                ipc_kernel_map, addr2, size_used,
        !          1946:                                TRUE, &memory2);
        !          1947:                assert(kr == KERN_SUCCESS);
        !          1948: #endif
        !          1949: 
        !          1950:                if (size_used != size2)
        !          1951:                        kmem_free(
        !          1952:                                ipc_kernel_map,
        !          1953:                                addr2 + size_used, size2 - size_used);
        !          1954: 
        !          1955:                *chunksp = (zone_free_space_chunk_t *)memory2;
        !          1956:        }
        !          1957:        else if (actual2 == 0) {
        !          1958: #if    MACH_OLD_VM_COPY
        !          1959:                *chunksp = (zone_free_space_chunk_t *)0;
        !          1960: #else
        !          1961:                *chunksp = (zone_free_space_chunk_t *)VM_MAP_COPY_NULL;
        !          1962: #endif
        !          1963: 
        !          1964:                if (size2 != 0)
        !          1965:                        kmem_free(ipc_kernel_map, addr2, size2);
        !          1966:        }
        !          1967: 
        !          1968:        *chunksCnt = actual2;
        !          1969: 
        !          1970:        return KERN_SUCCESS;
        !          1971: }
        !          1972: 
        !          1973: kern_return_t host_zone_collect(
        !          1974:        host_t          host,
        !          1975:        boolean_t       collect_zones,
        !          1976:        boolean_t       reclaim_pages)
        !          1977: {
        !          1978:        struct zone_free_space_entry
        !          1979:                        *cur, *pages = 0;
        !          1980:        zone_t          z;
        !          1981:        int             max_zones, i;
        !          1982: 
        !          1983:        if (host == HOST_NULL)
        !          1984:                return KERN_INVALID_HOST;
        !          1985: 
        !          1986:        if (!collect_zones)
        !          1987:            return KERN_SUCCESS;
        !          1988:        
        !          1989:        simple_lock(simple_lock_addr(zget_space_lock));
        !          1990: 
        !          1991:        simple_lock(simple_lock_addr(all_zones_lock));
        !          1992:        max_zones = num_zones;
        !          1993:        z = first_zone;
        !          1994:        simple_unlock(simple_lock_addr(all_zones_lock));
        !          1995: 
        !          1996:        for (i = 0; i < max_zones; i++) {
        !          1997:                assert(z != ZONE_NULL);
        !          1998:        /* run this at splhigh so that interupt routines that use zones
        !          1999:           can not interupt while their zone is locked */
        !          2000:                lock_zone(z);
        !          2001: 
        !          2002:                if (!z->pageable && zone_collectable(z))
        !          2003:                    zone_collect(z);
        !          2004: 
        !          2005:                unlock_zone(z);         
        !          2006:                simple_lock(simple_lock_addr(all_zones_lock));
        !          2007:                z = z->next_zone;
        !          2008:                simple_unlock(simple_lock_addr(all_zones_lock));
        !          2009:        }
        !          2010: 
        !          2011:        if (reclaim_pages)
        !          2012:                pages = zone_free_space_reclaim();
        !          2013:        
        !          2014:        simple_unlock(simple_lock_addr(zget_space_lock));
        !          2015: 
        !          2016:        /*
        !          2017:         * Return any reclaimed pages to
        !          2018:         * the system.
        !          2019:         */
        !          2020:        while ((cur = pages) != 0) {
        !          2021:                pages = cur->next;
        !          2022:                kmem_free(zone_map, (vm_offset_t)cur, cur->length);
        !          2023:        }
        !          2024: 
        !          2025:        return KERN_SUCCESS;
        !          2026: }
        !          2027: #endif MACH_DEBUG

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