Return to ipc_hash.c CVS log

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

Annotation of XNU/osfmk/ipc/ipc_hash.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * The contents of this file constitute Original Code as defined in and
        !             7:  * are subject to the Apple Public Source License Version 1.1 (the
        !             8:  * "License").  You may not use this file except in compliance with the
        !             9:  * License.  Please obtain a copy of the License at
        !            10:  * http://www.apple.com/publicsource and read it before using this file.
        !            11:  * 
        !            12:  * This Original Code and all software distributed under the License are
        !            13:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            14:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            15:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            16:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            17:  * License for the specific language governing rights and limitations
        !            18:  * under the License.
        !            19:  * 
        !            20:  * @APPLE_LICENSE_HEADER_END@
        !            21:  */
        !            22: /*
        !            23:  * @OSF_COPYRIGHT@
        !            24:  */
        !            25: /* 
        !            26:  * Mach Operating System
        !            27:  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
        !            28:  * All Rights Reserved.
        !            29:  * 
        !            30:  * Permission to use, copy, modify and distribute this software and its
        !            31:  * documentation is hereby granted, provided that both the copyright
        !            32:  * notice and this permission notice appear in all copies of the
        !            33:  * software, derivative works or modified versions, and any portions
        !            34:  * thereof, and that both notices appear in supporting documentation.
        !            35:  * 
        !            36:  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
        !            37:  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
        !            38:  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
        !            39:  * 
        !            40:  * Carnegie Mellon requests users of this software to return to
        !            41:  * 
        !            42:  *  Software Distribution Coordinator  or  [email protected]
        !            43:  *  School of Computer Science
        !            44:  *  Carnegie Mellon University
        !            45:  *  Pittsburgh PA 15213-3890
        !            46:  * 
        !            47:  * any improvements or extensions that they make and grant Carnegie Mellon
        !            48:  * the rights to redistribute these changes.
        !            49:  */
        !            50: /*
        !            51:  */
        !            52: /*
        !            53:  *     File:   ipc/ipc_hash.c
        !            54:  *     Author: Rich Draves
        !            55:  *     Date:   1989
        !            56:  *
        !            57:  *     Entry hash table operations.
        !            58:  */
        !            59: 
        !            60: #include <mach/boolean.h>
        !            61: #include <mach/port.h>
        !            62: #include <kern/lock.h>
        !            63: #include <kern/kalloc.h>
        !            64: #include <ipc/port.h>
        !            65: #include <ipc/ipc_space.h>
        !            66: #include <ipc/ipc_object.h>
        !            67: #include <ipc/ipc_entry.h>
        !            68: #include <ipc/ipc_hash.h>
        !            69: #include <ipc/ipc_init.h>
        !            70: 
        !            71: #include <mach_ipc_debug.h>
        !            72: 
        !            73: #if    MACH_IPC_DEBUG
        !            74: #include <mach/kern_return.h>
        !            75: #include <mach_debug/hash_info.h>
        !            76: #include <vm/vm_map.h>
        !            77: #include <vm/vm_kern.h>
        !            78: #include <vm/vm_user.h>
        !            79: #endif /* MACH_IPC_DEBUG */
        !            80: 
        !            81: /*
        !            82:  * Forward declarations 
        !            83:  */
        !            84: 
        !            85: /* Lookup (space, obj) in global hash table */
        !            86: boolean_t ipc_hash_global_lookup(
        !            87:        ipc_space_t             space,
        !            88:        ipc_object_t            obj,
        !            89:        mach_port_name_t        *namep,
        !            90:        ipc_tree_entry_t        *entryp);
        !            91: 
        !            92: /* Insert an entry into the global reverse hash table */
        !            93: void ipc_hash_global_insert(
        !            94:        ipc_space_t             space,
        !            95:        ipc_object_t            obj,
        !            96:        mach_port_name_t        name,
        !            97:        ipc_tree_entry_t        entry);
        !            98: 
        !            99: /* Delete an entry from the local reverse hash table */
        !           100: void ipc_hash_local_delete(
        !           101:        ipc_space_t             space,
        !           102:        ipc_object_t            obj,
        !           103:        mach_port_index_t       index,
        !           104:        ipc_entry_t             entry);
        !           105: 
        !           106: /*
        !           107:  *     Routine:        ipc_hash_lookup
        !           108:  *     Purpose:
        !           109:  *             Converts (space, obj) -> (name, entry).
        !           110:  *             Returns TRUE if an entry was found.
        !           111:  *     Conditions:
        !           112:  *             The space must be locked (read or write) throughout.
        !           113:  */
        !           114: 
        !           115: boolean_t
        !           116: ipc_hash_lookup(
        !           117:        ipc_space_t             space,
        !           118:        ipc_object_t            obj,
        !           119:        mach_port_name_t        *namep,
        !           120:        ipc_entry_t             *entryp)
        !           121: {
        !           122:        boolean_t       rv;
        !           123: 
        !           124:        rv = ipc_hash_local_lookup(space, obj, namep, entryp);
        !           125:        if (!rv) {
        !           126:                assert(!is_fast_space(space) || space->is_tree_hash == 0);
        !           127:                if (space->is_tree_hash > 0)
        !           128:                        rv = ipc_hash_global_lookup(space, obj, namep,
        !           129:                                (ipc_tree_entry_t *) entryp);
        !           130:        }
        !           131:        return (rv);
        !           132: }
        !           133: 
        !           134: /*
        !           135:  *     Routine:        ipc_hash_insert
        !           136:  *     Purpose:
        !           137:  *             Inserts an entry into the appropriate reverse hash table,
        !           138:  *             so that ipc_hash_lookup will find it.
        !           139:  *     Conditions:
        !           140:  *             The space must be write-locked.
        !           141:  */
        !           142: 
        !           143: void
        !           144: ipc_hash_insert(
        !           145:        ipc_space_t             space,
        !           146:        ipc_object_t            obj,
        !           147:        mach_port_name_t        name,
        !           148:        ipc_entry_t             entry)
        !           149: {
        !           150:        mach_port_index_t index;
        !           151: 
        !           152:        index = MACH_PORT_INDEX(name);
        !           153:        if ((index < space->is_table_size) &&
        !           154:            (entry == &space->is_table[index]))
        !           155:                ipc_hash_local_insert(space, obj, index, entry);
        !           156:        else {
        !           157:                assert(!is_fast_space(space));
        !           158:                ipc_hash_global_insert(space, obj, name,
        !           159:                                       (ipc_tree_entry_t) entry);
        !           160:        }
        !           161: }
        !           162: 
        !           163: /*
        !           164:  *     Routine:        ipc_hash_delete
        !           165:  *     Purpose:
        !           166:  *             Deletes an entry from the appropriate reverse hash table.
        !           167:  *     Conditions:
        !           168:  *             The space must be write-locked.
        !           169:  */
        !           170: 
        !           171: void
        !           172: ipc_hash_delete(
        !           173:        ipc_space_t             space,
        !           174:        ipc_object_t            obj,
        !           175:        mach_port_name_t        name,
        !           176:        ipc_entry_t             entry)
        !           177: {
        !           178:        mach_port_index_t index;
        !           179: 
        !           180:        index = MACH_PORT_INDEX(name);
        !           181:        if ((index < space->is_table_size) &&
        !           182:            (entry == &space->is_table[index]))
        !           183:                ipc_hash_local_delete(space, obj, index, entry);
        !           184:        else {
        !           185:                assert(!is_fast_space(space));
        !           186:                ipc_hash_global_delete(space, obj, name,
        !           187:                                       (ipc_tree_entry_t) entry);
        !           188:        }
        !           189: }
        !           190: 
        !           191: /*
        !           192:  *     The global reverse hash table holds splay tree entries.
        !           193:  *     It is a simple open-chaining hash table with singly-linked buckets.
        !           194:  *     Each bucket is locked separately, with an exclusive lock.
        !           195:  *     Within each bucket, move-to-front is used.
        !           196:  */
        !           197: 
        !           198: typedef natural_t ipc_hash_index_t;
        !           199: 
        !           200: ipc_hash_index_t ipc_hash_global_size;
        !           201: ipc_hash_index_t ipc_hash_global_mask;
        !           202: 
        !           203: #define IH_GLOBAL_HASH(space, obj)                                     \
        !           204:        (((((ipc_hash_index_t) ((vm_offset_t)space)) >> 4) +            \
        !           205:          (((ipc_hash_index_t) ((vm_offset_t)obj)) >> 6)) &             \
        !           206:         ipc_hash_global_mask)
        !           207: 
        !           208: typedef struct ipc_hash_global_bucket {
        !           209:        decl_mutex_data(,       ihgb_lock_data)
        !           210:        ipc_tree_entry_t        ihgb_head;
        !           211: } *ipc_hash_global_bucket_t;
        !           212: 
        !           213: #define        IHGB_NULL       ((ipc_hash_global_bucket_t) 0)
        !           214: 
        !           215: #define        ihgb_lock_init(ihgb)    mutex_init(&(ihgb)->ihgb_lock_data, \
        !           216:                                           ETAP_IPC_IHGB)
        !           217: #define        ihgb_lock(ihgb)         mutex_lock(&(ihgb)->ihgb_lock_data)
        !           218: #define        ihgb_unlock(ihgb)       mutex_unlock(&(ihgb)->ihgb_lock_data)
        !           219: 
        !           220: ipc_hash_global_bucket_t ipc_hash_global_table;
        !           221: 
        !           222: /*
        !           223:  *     Routine:        ipc_hash_global_lookup
        !           224:  *     Purpose:
        !           225:  *             Converts (space, obj) -> (name, entry).
        !           226:  *             Looks in the global table, for splay tree entries.
        !           227:  *             Returns TRUE if an entry was found.
        !           228:  *     Conditions:
        !           229:  *             The space must be locked (read or write) throughout.
        !           230:  */
        !           231: 
        !           232: boolean_t
        !           233: ipc_hash_global_lookup(
        !           234:        ipc_space_t                     space,
        !           235:        ipc_object_t                    obj,
        !           236:        mach_port_name_t                *namep,
        !           237:        ipc_tree_entry_t                *entryp)
        !           238: {
        !           239:        ipc_hash_global_bucket_t bucket;
        !           240:        ipc_tree_entry_t this, *last;
        !           241: 
        !           242:        assert(space != IS_NULL);
        !           243:        assert(obj != IO_NULL);
        !           244: 
        !           245:        assert(!is_fast_space(space));
        !           246:        bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
        !           247:        ihgb_lock(bucket);
        !           248: 
        !           249:        if ((this = bucket->ihgb_head) != ITE_NULL) {
        !           250:                if ((this->ite_object == obj) &&
        !           251:                    (this->ite_space == space)) {
        !           252:                        /* found it at front; no need to move */
        !           253: 
        !           254:                        *namep = this->ite_name;
        !           255:                        *entryp = this;
        !           256:                } else for (last = &this->ite_next;
        !           257:                            (this = *last) != ITE_NULL;
        !           258:                            last = &this->ite_next) {
        !           259:                        if ((this->ite_object == obj) &&
        !           260:                            (this->ite_space == space)) {
        !           261:                                /* found it; move to front */
        !           262: 
        !           263:                                *last = this->ite_next;
        !           264:                                this->ite_next = bucket->ihgb_head;
        !           265:                                bucket->ihgb_head = this;
        !           266: 
        !           267:                                *namep = this->ite_name;
        !           268:                                *entryp = this;
        !           269:                                break;
        !           270:                        }
        !           271:                }
        !           272:        }
        !           273: 
        !           274:        ihgb_unlock(bucket);
        !           275:        return this != ITE_NULL;
        !           276: }
        !           277: 
        !           278: /*
        !           279:  *     Routine:        ipc_hash_global_insert
        !           280:  *     Purpose:
        !           281:  *             Inserts an entry into the global reverse hash table.
        !           282:  *     Conditions:
        !           283:  *             The space must be write-locked.
        !           284:  */
        !           285: 
        !           286: void
        !           287: ipc_hash_global_insert(
        !           288:        ipc_space_t                     space,
        !           289:        ipc_object_t                    obj,
        !           290:        mach_port_name_t                name,
        !           291:        ipc_tree_entry_t                entry)
        !           292: {
        !           293:        ipc_hash_global_bucket_t bucket;
        !           294: 
        !           295: 
        !           296:        assert(!is_fast_space(space));
        !           297: 
        !           298: 
        !           299:        assert(entry->ite_name == name);
        !           300:        assert(space != IS_NULL);
        !           301:        assert(entry->ite_space == space);
        !           302:        assert(obj != IO_NULL);
        !           303:        assert(entry->ite_object == obj);
        !           304: 
        !           305:        space->is_tree_hash++;
        !           306:        assert(space->is_tree_hash <= space->is_tree_total);
        !           307: 
        !           308:        bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
        !           309:        ihgb_lock(bucket);
        !           310: 
        !           311:        /* insert at front of bucket */
        !           312: 
        !           313:        entry->ite_next = bucket->ihgb_head;
        !           314:        bucket->ihgb_head = entry;
        !           315: 
        !           316:        ihgb_unlock(bucket);
        !           317: }
        !           318: 
        !           319: /*
        !           320:  *     Routine:        ipc_hash_global_delete
        !           321:  *     Purpose:
        !           322:  *             Deletes an entry from the global reverse hash table.
        !           323:  *     Conditions:
        !           324:  *             The space must be write-locked.
        !           325:  */
        !           326: 
        !           327: void
        !           328: ipc_hash_global_delete(
        !           329:        ipc_space_t                     space,
        !           330:        ipc_object_t                    obj,
        !           331:        mach_port_name_t                name,
        !           332:        ipc_tree_entry_t                entry)
        !           333: {
        !           334:        ipc_hash_global_bucket_t bucket;
        !           335:        ipc_tree_entry_t this, *last;
        !           336: 
        !           337:        assert(!is_fast_space(space));
        !           338: 
        !           339:        assert(entry->ite_name == name);
        !           340:        assert(space != IS_NULL);
        !           341:        assert(entry->ite_space == space);
        !           342:        assert(obj != IO_NULL);
        !           343:        assert(entry->ite_object == obj);
        !           344: 
        !           345:        assert(space->is_tree_hash > 0);
        !           346:        space->is_tree_hash--;
        !           347: 
        !           348:        bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
        !           349:        ihgb_lock(bucket);
        !           350: 
        !           351:        for (last = &bucket->ihgb_head;
        !           352:             (this = *last) != ITE_NULL;
        !           353:             last = &this->ite_next) {
        !           354:                if (this == entry) {
        !           355:                        /* found it; remove from bucket */
        !           356: 
        !           357:                        *last = this->ite_next;
        !           358:                        break;
        !           359:                }
        !           360:        }
        !           361:        assert(this != ITE_NULL);
        !           362: 
        !           363:        ihgb_unlock(bucket);
        !           364: }
        !           365: 
        !           366: /*
        !           367:  *     Each space has a local reverse hash table, which holds
        !           368:  *     entries from the space's table.  In fact, the hash table
        !           369:  *     just uses a field (ie_index) in the table itself.
        !           370:  *
        !           371:  *     The local hash table is an open-addressing hash table,
        !           372:  *     which means that when a collision occurs, instead of
        !           373:  *     throwing the entry into a bucket, the entry is rehashed
        !           374:  *     to another position in the table.  In this case the rehash
        !           375:  *     is very simple: linear probing (ie, just increment the position).
        !           376:  *     This simple rehash makes deletions tractable (they're still a pain),
        !           377:  *     but it means that collisions tend to build up into clumps.
        !           378:  *
        !           379:  *     Because at least one entry in the table (index 0) is always unused,
        !           380:  *     there will always be room in the reverse hash table.  If a table
        !           381:  *     with n slots gets completely full, the reverse hash table will
        !           382:  *     have one giant clump of n-1 slots and one free slot somewhere.
        !           383:  *     Because entries are only entered into the reverse table if they
        !           384:  *     are pure send rights (not receive, send-once, port-set,
        !           385:  *     or dead-name rights), and free entries of course aren't entered,
        !           386:  *     I expect the reverse hash table won't get unreasonably full.
        !           387:  *
        !           388:  *     Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2,
        !           389:  *     pp. 135-142.) may be desirable here.  They can dramatically help
        !           390:  *     unsuccessful lookups.  But unsuccessful lookups are almost always
        !           391:  *     followed by insertions, and those slow down somewhat.  They
        !           392:  *     also can help deletions somewhat.  Successful lookups aren't affected.
        !           393:  *     So possibly a small win; probably nothing significant.
        !           394:  */
        !           395: 
        !           396: #define        IH_LOCAL_HASH(obj, size)                                \
        !           397:                ((((mach_port_index_t) (obj)) >> 6) % (size))
        !           398: 
        !           399: /*
        !           400:  *     Routine:        ipc_hash_local_lookup
        !           401:  *     Purpose:
        !           402:  *             Converts (space, obj) -> (name, entry).
        !           403:  *             Looks in the space's local table, for table entries.
        !           404:  *             Returns TRUE if an entry was found.
        !           405:  *     Conditions:
        !           406:  *             The space must be locked (read or write) throughout.
        !           407:  */
        !           408: 
        !           409: boolean_t
        !           410: ipc_hash_local_lookup(
        !           411:        ipc_space_t             space,
        !           412:        ipc_object_t            obj,
        !           413:        mach_port_name_t        *namep,
        !           414:        ipc_entry_t             *entryp)
        !           415: {
        !           416:        ipc_entry_t table;
        !           417:        ipc_entry_num_t size;
        !           418:        mach_port_index_t hindex, index;
        !           419: 
        !           420:        assert(space != IS_NULL);
        !           421:        assert(obj != IO_NULL);
        !           422: 
        !           423:        table = space->is_table;
        !           424:        size = space->is_table_size;
        !           425:        hindex = IH_LOCAL_HASH(obj, size);
        !           426: 
        !           427:        /*
        !           428:         *      Ideally, table[hindex].ie_index is the name we want.
        !           429:         *      However, must check ie_object to verify this,
        !           430:         *      because collisions can happen.  In case of a collision,
        !           431:         *      search farther along in the clump.
        !           432:         */
        !           433: 
        !           434:        while ((index = table[hindex].ie_index) != 0) {
        !           435:                ipc_entry_t entry = &table[index];
        !           436: 
        !           437:                if (entry->ie_object == obj) {
        !           438:                        *entryp = entry;
        !           439:                        *namep = MACH_PORT_MAKE(index,
        !           440:                                                IE_BITS_GEN(entry->ie_bits));
        !           441:                        return TRUE;
        !           442:                }
        !           443: 
        !           444:                if (++hindex == size)
        !           445:                        hindex = 0;
        !           446:        }
        !           447: 
        !           448:        return FALSE;
        !           449: }
        !           450: 
        !           451: /*
        !           452:  *     Routine:        ipc_hash_local_insert
        !           453:  *     Purpose:
        !           454:  *             Inserts an entry into the space's reverse hash table.
        !           455:  *     Conditions:
        !           456:  *             The space must be write-locked.
        !           457:  */
        !           458: 
        !           459: void
        !           460: ipc_hash_local_insert(
        !           461:        ipc_space_t             space,
        !           462:        ipc_object_t            obj,
        !           463:        mach_port_index_t       index,
        !           464:        ipc_entry_t             entry)
        !           465: {
        !           466:        ipc_entry_t table;
        !           467:        ipc_entry_num_t size;
        !           468:        mach_port_index_t hindex;
        !           469: 
        !           470:        assert(index != 0);
        !           471:        assert(space != IS_NULL);
        !           472:        assert(obj != IO_NULL);
        !           473: 
        !           474:        table = space->is_table;
        !           475:        size = space->is_table_size;
        !           476:        hindex = IH_LOCAL_HASH(obj, size);
        !           477: 
        !           478:        assert(entry == &table[index]);
        !           479:        assert(entry->ie_object == obj);
        !           480: 
        !           481:        /*
        !           482:         *      We want to insert at hindex, but there may be collisions.
        !           483:         *      If a collision occurs, search for the end of the clump
        !           484:         *      and insert there.
        !           485:         */
        !           486: 
        !           487:        while (table[hindex].ie_index != 0) {
        !           488:                if (++hindex == size)
        !           489:                        hindex = 0;
        !           490:        }
        !           491: 
        !           492:        table[hindex].ie_index = index;
        !           493: }
        !           494: 
        !           495: /*
        !           496:  *     Routine:        ipc_hash_local_delete
        !           497:  *     Purpose:
        !           498:  *             Deletes an entry from the space's reverse hash table.
        !           499:  *     Conditions:
        !           500:  *             The space must be write-locked.
        !           501:  */
        !           502: 
        !           503: void
        !           504: ipc_hash_local_delete(
        !           505:        ipc_space_t             space,
        !           506:        ipc_object_t            obj,
        !           507:        mach_port_index_t       index,
        !           508:        ipc_entry_t             entry)
        !           509: {
        !           510:        ipc_entry_t table;
        !           511:        ipc_entry_num_t size;
        !           512:        mach_port_index_t hindex, dindex;
        !           513: 
        !           514:        assert(index != MACH_PORT_NULL);
        !           515:        assert(space != IS_NULL);
        !           516:        assert(obj != IO_NULL);
        !           517: 
        !           518:        table = space->is_table;
        !           519:        size = space->is_table_size;
        !           520:        hindex = IH_LOCAL_HASH(obj, size);
        !           521: 
        !           522:        assert(entry == &table[index]);
        !           523:        assert(entry->ie_object == obj);
        !           524: 
        !           525:        /*
        !           526:         *      First check we have the right hindex for this index.
        !           527:         *      In case of collision, we have to search farther
        !           528:         *      along in this clump.
        !           529:         */
        !           530: 
        !           531:        while (table[hindex].ie_index != index) {
        !           532:                if (++hindex == size)
        !           533:                        hindex = 0;
        !           534:        }
        !           535: 
        !           536:        /*
        !           537:         *      Now we want to set table[hindex].ie_index = 0.
        !           538:         *      But if we aren't the last index in a clump,
        !           539:         *      this might cause problems for lookups of objects
        !           540:         *      farther along in the clump that are displaced
        !           541:         *      due to collisions.  Searches for them would fail
        !           542:         *      at hindex instead of succeeding.
        !           543:         *
        !           544:         *      So we must check the clump after hindex for objects
        !           545:         *      that are so displaced, and move one up to the new hole.
        !           546:         *
        !           547:         *              hindex - index of new hole in the clump
        !           548:         *              dindex - index we are checking for a displaced object
        !           549:         *
        !           550:         *      When we move a displaced object up into the hole,
        !           551:         *      it creates a new hole, and we have to repeat the process
        !           552:         *      until we get to the end of the clump.
        !           553:         */
        !           554: 
        !           555:        for (dindex = hindex; index != 0; hindex = dindex) {
        !           556:                for (;;) {
        !           557:                        mach_port_index_t tindex;
        !           558:                        ipc_object_t tobj;
        !           559: 
        !           560:                        if (++dindex == size)
        !           561:                                dindex = 0;
        !           562:                        assert(dindex != hindex);
        !           563: 
        !           564:                        /* are we at the end of the clump? */
        !           565: 
        !           566:                        index = table[dindex].ie_index;
        !           567:                        if (index == 0)
        !           568:                                break;
        !           569: 
        !           570:                        /* is this a displaced object? */
        !           571: 
        !           572:                        tobj = table[index].ie_object;
        !           573:                        assert(tobj != IO_NULL);
        !           574:                        tindex = IH_LOCAL_HASH(tobj, size);
        !           575: 
        !           576:                        if ((dindex < hindex) ?
        !           577:                            ((dindex < tindex) && (tindex <= hindex)) :
        !           578:                            ((dindex < tindex) || (tindex <= hindex)))
        !           579:                                break;
        !           580:                }
        !           581: 
        !           582:                table[hindex].ie_index = index;
        !           583:        }
        !           584: }
        !           585: 
        !           586: /*
        !           587:  *     Routine:        ipc_hash_init
        !           588:  *     Purpose:
        !           589:  *             Initialize the reverse hash table implementation.
        !           590:  */
        !           591: 
        !           592: void
        !           593: ipc_hash_init(void)
        !           594: {
        !           595:        ipc_hash_index_t i;
        !           596: 
        !           597:        /* if not configured, initialize ipc_hash_global_size */
        !           598: 
        !           599:        if (ipc_hash_global_size == 0) {
        !           600:                ipc_hash_global_size = ipc_tree_entry_max >> 8;
        !           601:                if (ipc_hash_global_size < 32)
        !           602:                        ipc_hash_global_size = 32;
        !           603:        }
        !           604: 
        !           605:        /* make sure it is a power of two */
        !           606: 
        !           607:        ipc_hash_global_mask = ipc_hash_global_size - 1;
        !           608:        if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) {
        !           609:                natural_t bit;
        !           610: 
        !           611:                /* round up to closest power of two */
        !           612: 
        !           613:                for (bit = 1;; bit <<= 1) {
        !           614:                        ipc_hash_global_mask |= bit;
        !           615:                        ipc_hash_global_size = ipc_hash_global_mask + 1;
        !           616: 
        !           617:                        if ((ipc_hash_global_size & ipc_hash_global_mask) == 0)
        !           618:                                break;
        !           619:                }
        !           620:        }
        !           621: 
        !           622:        /* allocate ipc_hash_global_table */
        !           623: 
        !           624:        ipc_hash_global_table = (ipc_hash_global_bucket_t)
        !           625:                kalloc((vm_size_t) (ipc_hash_global_size *
        !           626:                                    sizeof(struct ipc_hash_global_bucket)));
        !           627:        assert(ipc_hash_global_table != IHGB_NULL);
        !           628: 
        !           629:        /* and initialize it */
        !           630: 
        !           631:        for (i = 0; i < ipc_hash_global_size; i++) {
        !           632:                ipc_hash_global_bucket_t bucket;
        !           633: 
        !           634:                bucket = &ipc_hash_global_table[i];
        !           635:                ihgb_lock_init(bucket);
        !           636:                bucket->ihgb_head = ITE_NULL;
        !           637:        }
        !           638: }
        !           639: 
        !           640: #if    MACH_IPC_DEBUG
        !           641: 
        !           642: /*
        !           643:  *     Routine:        ipc_hash_info
        !           644:  *     Purpose:
        !           645:  *             Return information about the global reverse hash table.
        !           646:  *             Fills the buffer with as much information as possible
        !           647:  *             and returns the desired size of the buffer.
        !           648:  *     Conditions:
        !           649:  *             Nothing locked.  The caller should provide
        !           650:  *             possibly-pageable memory.
        !           651:  */
        !           652: 
        !           653: 
        !           654: ipc_hash_index_t
        !           655: ipc_hash_info(
        !           656:        hash_info_bucket_t      *info,
        !           657:        mach_msg_type_number_t count)
        !           658: {
        !           659:        ipc_hash_index_t i;
        !           660: 
        !           661:        if (ipc_hash_global_size < count)
        !           662:                count = ipc_hash_global_size;
        !           663: 
        !           664:        for (i = 0; i < count; i++) {
        !           665:                ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i];
        !           666:                unsigned int bucket_count = 0;
        !           667:                ipc_tree_entry_t entry;
        !           668: 
        !           669:                ihgb_lock(bucket);
        !           670:                for (entry = bucket->ihgb_head;
        !           671:                     entry != ITE_NULL;
        !           672:                     entry = entry->ite_next)
        !           673:                        bucket_count++;
        !           674:                ihgb_unlock(bucket);
        !           675: 
        !           676:                /* don't touch pageable memory while holding locks */
        !           677:                info[i].hib_count = bucket_count;
        !           678:        }
        !           679: 
        !           680:        return ipc_hash_global_size;
        !           681: }
        !           682: 
        !           683: #endif /* MACH_IPC_DEBUG */

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