Return to ipc_hash.c CVS log

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

Annotation of kernel/ipc/ipc_hash.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:  * Copyright (c) 1995, 1994, 1993, 1992, 1991, 1990  
        !            27:  * Open Software Foundation, Inc. 
        !            28:  *  
        !            29:  * Permission to use, copy, modify, and distribute this software and 
        !            30:  * its documentation for any purpose and without fee is hereby granted, 
        !            31:  * provided that the above copyright notice appears in all copies and 
        !            32:  * that both the copyright notice and this permission notice appear in 
        !            33:  * supporting documentation, and that the name of ("OSF") or Open Software 
        !            34:  * Foundation not be used in advertising or publicity pertaining to 
        !            35:  * distribution of the software without specific, written prior permission. 
        !            36:  *  
        !            37:  * OSF DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE 
        !            38:  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
        !            39:  * FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL OSF BE LIABLE FOR ANY 
        !            40:  * SPECIAL, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 
        !            41:  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
        !            42:  * ACTION OF CONTRACT, NEGLIGENCE, OR OTHER TORTIOUS ACTION, ARISING 
        !            43:  * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE 
        !            44:  */
        !            45: /*
        !            46:  * OSF Research Institute MK6.1 (unencumbered) 1/31/1995
        !            47:  */
        !            48: /* 
        !            49:  * Mach Operating System
        !            50:  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
        !            51:  * All Rights Reserved.
        !            52:  * 
        !            53:  * Permission to use, copy, modify and distribute this software and its
        !            54:  * documentation is hereby granted, provided that both the copyright
        !            55:  * notice and this permission notice appear in all copies of the
        !            56:  * software, derivative works or modified versions, and any portions
        !            57:  * thereof, and that both notices appear in supporting documentation.
        !            58:  * 
        !            59:  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
        !            60:  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
        !            61:  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
        !            62:  * 
        !            63:  * Carnegie Mellon requests users of this software to return to
        !            64:  * 
        !            65:  *  Software Distribution Coordinator  or  [email protected]
        !            66:  *  School of Computer Science
        !            67:  *  Carnegie Mellon University
        !            68:  *  Pittsburgh PA 15213-3890
        !            69:  * 
        !            70:  * any improvements or extensions that they make and grant Carnegie Mellon
        !            71:  * the rights to redistribute these changes.
        !            72:  */
        !            73: /*
        !            74:  *     File:   ipc/ipc_hash.c
        !            75:  *     Author: Rich Draves
        !            76:  *     Date:   1989
        !            77:  *
        !            78:  *     Entry hash table operations.
        !            79:  */
        !            80: 
        !            81: #include <mach/boolean.h>
        !            82: #include <mach/port.h>
        !            83: #include <kern/lock.h>
        !            84: #include <kern/kalloc.h>
        !            85: #include <ipc/port.h>
        !            86: #include <ipc/ipc_space.h>
        !            87: #include <ipc/ipc_object.h>
        !            88: #include <ipc/ipc_entry.h>
        !            89: #include <ipc/ipc_hash.h>
        !            90: #include <ipc/ipc_init.h>
        !            91: 
        !            92: /*
        !            93:  * Forward declarations 
        !            94:  */
        !            95: 
        !            96: /* Lookup (space, obj) in global hash table */
        !            97: boolean_t ipc_hash_global_lookup(
        !            98:        ipc_space_t             space,
        !            99:        ipc_object_t            obj,
        !           100:        mach_port_t             *namep,
        !           101:        ipc_tree_entry_t        *entryp);
        !           102: 
        !           103: /* Insert an entry into the global reverse hash table */
        !           104: void ipc_hash_global_insert(
        !           105:        ipc_space_t             space,
        !           106:        ipc_object_t            obj,
        !           107:        mach_port_t             name,
        !           108:        ipc_tree_entry_t        entry);
        !           109: 
        !           110: /* Delete an entry from the local reverse hash table */
        !           111: void ipc_hash_local_delete(
        !           112:        ipc_space_t             space,
        !           113:        ipc_object_t            obj,
        !           114:        mach_port_index_t       index,
        !           115:        ipc_entry_t             entry);
        !           116: 
        !           117: /*
        !           118:  *     Routine:        ipc_hash_lookup
        !           119:  *     Purpose:
        !           120:  *             Converts (space, obj) -> (name, entry).
        !           121:  *             Returns TRUE if an entry was found.
        !           122:  *     Conditions:
        !           123:  *             The space must be locked (read or write) throughout.
        !           124:  */
        !           125: 
        !           126: boolean_t
        !           127: ipc_hash_lookup(
        !           128:        ipc_space_t     space,
        !           129:        ipc_object_t    obj,
        !           130:        mach_port_t     *namep,
        !           131:        ipc_entry_t     *entryp)
        !           132: {
        !           133:        boolean_t       rv;
        !           134: 
        !           135:        rv = ipc_hash_local_lookup(space, obj, namep, entryp);
        !           136:        if (!rv) {
        !           137:                if (space->is_tree_hash > 0)
        !           138:                        rv = ipc_hash_global_lookup(space, obj, namep,
        !           139:                                (ipc_tree_entry_t *) entryp);
        !           140:        }
        !           141:        return (rv);
        !           142: }
        !           143: 
        !           144: /*
        !           145:  *     Routine:        ipc_hash_insert
        !           146:  *     Purpose:
        !           147:  *             Inserts an entry into the appropriate reverse hash table,
        !           148:  *             so that ipc_hash_lookup will find it.
        !           149:  *     Conditions:
        !           150:  *             The space must be write-locked.
        !           151:  */
        !           152: 
        !           153: void
        !           154: ipc_hash_insert(
        !           155:        ipc_space_t     space,
        !           156:        ipc_object_t    obj,
        !           157:        mach_port_t     name,
        !           158:        ipc_entry_t     entry)
        !           159: {
        !           160:        mach_port_index_t index;
        !           161: 
        !           162:        index = MACH_PORT_INDEX(name);
        !           163:        if ((index < space->is_table_size) &&
        !           164:            (entry == &space->is_table[index]))
        !           165:                ipc_hash_local_insert(space, obj, index, entry);
        !           166:        else {
        !           167:                ipc_hash_global_insert(space, obj, name,
        !           168:                                       (ipc_tree_entry_t) entry);
        !           169:        }
        !           170: }
        !           171: 
        !           172: /*
        !           173:  *     Routine:        ipc_hash_delete
        !           174:  *     Purpose:
        !           175:  *             Deletes an entry from the appropriate reverse hash table.
        !           176:  *     Conditions:
        !           177:  *             The space must be write-locked.
        !           178:  */
        !           179: 
        !           180: void
        !           181: ipc_hash_delete(
        !           182:        ipc_space_t     space,
        !           183:        ipc_object_t    obj,
        !           184:        mach_port_t     name,
        !           185:        ipc_entry_t     entry)
        !           186: {
        !           187:        mach_port_index_t index;
        !           188: 
        !           189:        index = MACH_PORT_INDEX(name);
        !           190:        if ((index < space->is_table_size) &&
        !           191:            (entry == &space->is_table[index]))
        !           192:                ipc_hash_local_delete(space, obj, index, entry);
        !           193:        else {
        !           194:                ipc_hash_global_delete(space, obj, name,
        !           195:                                       (ipc_tree_entry_t) entry);
        !           196:        }
        !           197: }
        !           198: 
        !           199: /*
        !           200:  *     The global reverse hash table holds splay tree entries.
        !           201:  *     It is a simple open-chaining hash table with singly-linked buckets.
        !           202:  *     Each bucket is locked separately, with an exclusive lock.
        !           203:  *     Within each bucket, move-to-front is used.
        !           204:  */
        !           205: 
        !           206: typedef unsigned int ipc_hash_index_t;
        !           207: 
        !           208: ipc_hash_index_t ipc_hash_global_size;
        !           209: ipc_hash_index_t ipc_hash_global_mask;
        !           210: 
        !           211: #define IH_GLOBAL_HASH(space, obj)                     \
        !           212:        (((((ipc_hash_index_t) (space)) >> 4) +         \
        !           213:          (((ipc_hash_index_t) (obj)) >> 6)) &          \
        !           214:         ipc_hash_global_mask)
        !           215: 
        !           216: typedef struct ipc_hash_global_bucket {
        !           217:        decl_simple_lock_data(, ihgb_lock_data)
        !           218:        ipc_tree_entry_t        ihgb_head;
        !           219: } *ipc_hash_global_bucket_t;
        !           220: 
        !           221: #define        IHGB_NULL       ((ipc_hash_global_bucket_t) 0)
        !           222: 
        !           223: #define        ihgb_lock_init(ihgb)    simple_lock_init(&(ihgb)->ihgb_lock_data)
        !           224: #define        ihgb_lock(ihgb)         simple_lock(&(ihgb)->ihgb_lock_data)
        !           225: #define        ihgb_unlock(ihgb)       simple_unlock(&(ihgb)->ihgb_lock_data)
        !           226: 
        !           227: ipc_hash_global_bucket_t ipc_hash_global_table;
        !           228: 
        !           229: /*
        !           230:  *     Routine:        ipc_hash_global_lookup
        !           231:  *     Purpose:
        !           232:  *             Converts (space, obj) -> (name, entry).
        !           233:  *             Looks in the global table, for splay tree entries.
        !           234:  *             Returns TRUE if an entry was found.
        !           235:  *     Conditions:
        !           236:  *             The space must be locked (read or write) throughout.
        !           237:  */
        !           238: 
        !           239: boolean_t
        !           240: ipc_hash_global_lookup(
        !           241:        ipc_space_t             space,
        !           242:        ipc_object_t            obj,
        !           243:        mach_port_t             *namep,
        !           244:        ipc_tree_entry_t        *entryp)
        !           245: {
        !           246:        ipc_hash_global_bucket_t bucket;
        !           247:        ipc_tree_entry_t this, *last;
        !           248: 
        !           249:        assert(space != IS_NULL);
        !           250:        assert(obj != IO_NULL);
        !           251: 
        !           252:        bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
        !           253:        ihgb_lock(bucket);
        !           254: 
        !           255:        if ((this = bucket->ihgb_head) != ITE_NULL) {
        !           256:                if ((this->ite_object == obj) &&
        !           257:                    (this->ite_space == space)) {
        !           258:                        /* found it at front; no need to move */
        !           259: 
        !           260:                        *namep = this->ite_name;
        !           261:                        *entryp = this;
        !           262:                } else for (last = &this->ite_next;
        !           263:                            (this = *last) != ITE_NULL;
        !           264:                            last = &this->ite_next) {
        !           265:                        if ((this->ite_object == obj) &&
        !           266:                            (this->ite_space == space)) {
        !           267:                                /* found it; move to front */
        !           268: 
        !           269:                                *last = this->ite_next;
        !           270:                                this->ite_next = bucket->ihgb_head;
        !           271:                                bucket->ihgb_head = this;
        !           272: 
        !           273:                                *namep = this->ite_name;
        !           274:                                *entryp = this;
        !           275:                                break;
        !           276:                        }
        !           277:                }
        !           278:        }
        !           279: 
        !           280:        ihgb_unlock(bucket);
        !           281:        return this != ITE_NULL;
        !           282: }
        !           283: 
        !           284: /*
        !           285:  *     Routine:        ipc_hash_global_insert
        !           286:  *     Purpose:
        !           287:  *             Inserts an entry into the global reverse hash table.
        !           288:  *     Conditions:
        !           289:  *             The space must be write-locked.
        !           290:  */
        !           291: 
        !           292: void
        !           293: ipc_hash_global_insert(
        !           294:        ipc_space_t             space,
        !           295:        ipc_object_t            obj,
        !           296:        mach_port_t             name,
        !           297:        ipc_tree_entry_t        entry)
        !           298: {
        !           299:        ipc_hash_global_bucket_t bucket;
        !           300: 
        !           301:        assert(entry->ite_name == name);
        !           302:        assert(space != IS_NULL);
        !           303:        assert(entry->ite_space == space);
        !           304:        assert(obj != IO_NULL);
        !           305:        assert(entry->ite_object == obj);
        !           306: 
        !           307:        space->is_tree_hash++;
        !           308:        assert(space->is_tree_hash <= space->is_tree_total);
        !           309: 
        !           310:        bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
        !           311:        ihgb_lock(bucket);
        !           312: 
        !           313:        /* insert at front of bucket */
        !           314: 
        !           315:        entry->ite_next = bucket->ihgb_head;
        !           316:        bucket->ihgb_head = entry;
        !           317: 
        !           318:        ihgb_unlock(bucket);
        !           319: }
        !           320: 
        !           321: /*
        !           322:  *     Routine:        ipc_hash_global_delete
        !           323:  *     Purpose:
        !           324:  *             Deletes an entry from the global reverse hash table.
        !           325:  *     Conditions:
        !           326:  *             The space must be write-locked.
        !           327:  */
        !           328: 
        !           329: void
        !           330: ipc_hash_global_delete(
        !           331:        ipc_space_t             space,
        !           332:        ipc_object_t            obj,
        !           333:        mach_port_t             name,
        !           334:        ipc_tree_entry_t        entry)
        !           335: {
        !           336:        ipc_hash_global_bucket_t bucket;
        !           337:        ipc_tree_entry_t this, *last;
        !           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_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:                        *namep = MACH_PORT_MAKEB(index, entry->ie_bits);
        !           439:                        *entryp = entry;
        !           440:                        return TRUE;
        !           441:                }
        !           442: 
        !           443:                if (++hindex == size)
        !           444:                        hindex = 0;
        !           445:        }
        !           446: 
        !           447:        return FALSE;
        !           448: }
        !           449: 
        !           450: /*
        !           451:  *     Routine:        ipc_hash_local_insert
        !           452:  *     Purpose:
        !           453:  *             Inserts an entry into the space's reverse hash table.
        !           454:  *     Conditions:
        !           455:  *             The space must be write-locked.
        !           456:  */
        !           457: 
        !           458: void
        !           459: ipc_hash_local_insert(
        !           460:        ipc_space_t             space,
        !           461:        ipc_object_t            obj,
        !           462:        mach_port_index_t       index,
        !           463:        ipc_entry_t             entry)
        !           464: {
        !           465:        ipc_entry_t table;
        !           466:        ipc_entry_num_t size;
        !           467:        mach_port_index_t hindex;
        !           468: 
        !           469:        assert(index != 0);
        !           470:        assert(space != IS_NULL);
        !           471:        assert(obj != IO_NULL);
        !           472: 
        !           473:        table = space->is_table;
        !           474:        size = space->is_table_size;
        !           475:        hindex = IH_LOCAL_HASH(obj, size);
        !           476: 
        !           477:        assert(entry == &table[index]);
        !           478:        assert(entry->ie_object == obj);
        !           479: 
        !           480:        /*
        !           481:         *      We want to insert at hindex, but there may be collisions.
        !           482:         *      If a collision occurs, search for the end of the clump
        !           483:         *      and insert there.
        !           484:         */
        !           485: 
        !           486:        while (table[hindex].ie_index != 0) {
        !           487:                if (++hindex == size)
        !           488:                        hindex = 0;
        !           489:        }
        !           490: 
        !           491:        table[hindex].ie_index = index;
        !           492: }
        !           493: 
        !           494: /*
        !           495:  *     Routine:        ipc_hash_local_delete
        !           496:  *     Purpose:
        !           497:  *             Deletes an entry from the space's reverse hash table.
        !           498:  *     Conditions:
        !           499:  *             The space must be write-locked.
        !           500:  */
        !           501: 
        !           502: void
        !           503: ipc_hash_local_delete(
        !           504:        ipc_space_t             space,
        !           505:        ipc_object_t            obj,
        !           506:        mach_port_index_t       index,
        !           507:        ipc_entry_t             entry)
        !           508: {
        !           509:        ipc_entry_t table;
        !           510:        ipc_entry_num_t size;
        !           511:        mach_port_index_t hindex, dindex;
        !           512: 
        !           513:        assert(index != MACH_PORT_NULL);
        !           514:        assert(space != IS_NULL);
        !           515:        assert(obj != IO_NULL);
        !           516: 
        !           517:        table = space->is_table;
        !           518:        size = space->is_table_size;
        !           519:        hindex = IH_LOCAL_HASH(obj, size);
        !           520: 
        !           521:        assert(entry == &table[index]);
        !           522:        assert(entry->ie_object == obj);
        !           523: 
        !           524:        /*
        !           525:         *      First check we have the right hindex for this index.
        !           526:         *      In case of collision, we have to search farther
        !           527:         *      along in this clump.
        !           528:         */
        !           529: 
        !           530:        while (table[hindex].ie_index != index) {
        !           531:                if (++hindex == size)
        !           532:                        hindex = 0;
        !           533:        }
        !           534: 
        !           535:        /*
        !           536:         *      Now we want to set table[hindex].ie_index = 0.
        !           537:         *      But if we aren't the last index in a clump,
        !           538:         *      this might cause problems for lookups of objects
        !           539:         *      farther along in the clump that are displaced
        !           540:         *      due to collisions.  Searches for them would fail
        !           541:         *      at hindex instead of succeeding.
        !           542:         *
        !           543:         *      So we must check the clump after hindex for objects
        !           544:         *      that are so displaced, and move one up to the new hole.
        !           545:         *
        !           546:         *              hindex - index of new hole in the clump
        !           547:         *              dindex - index we are checking for a displaced object
        !           548:         *
        !           549:         *      When we move a displaced object up into the hole,
        !           550:         *      it creates a new hole, and we have to repeat the process
        !           551:         *      until we get to the end of the clump.
        !           552:         */
        !           553: 
        !           554:        for (dindex = hindex; index != 0; hindex = dindex) {
        !           555:                for (;;) {
        !           556:                        mach_port_index_t tindex;
        !           557:                        ipc_object_t tobj;
        !           558: 
        !           559:                        if (++dindex == size)
        !           560:                                dindex = 0;
        !           561:                        assert(dindex != hindex);
        !           562: 
        !           563:                        /* are we at the end of the clump? */
        !           564: 
        !           565:                        index = table[dindex].ie_index;
        !           566:                        if (index == 0)
        !           567:                                break;
        !           568: 
        !           569:                        /* is this a displaced object? */
        !           570: 
        !           571:                        tobj = table[index].ie_object;
        !           572:                        assert(tobj != IO_NULL);
        !           573:                        tindex = IH_LOCAL_HASH(tobj, size);
        !           574: 
        !           575:                        if ((dindex < hindex) ?
        !           576:                            ((dindex < tindex) && (tindex <= hindex)) :
        !           577:                            ((dindex < tindex) || (tindex <= hindex)))
        !           578:                                break;
        !           579:                }
        !           580: 
        !           581:                table[hindex].ie_index = index;
        !           582:        }
        !           583: }
        !           584: 
        !           585: /*
        !           586:  *     Routine:        ipc_hash_init
        !           587:  *     Purpose:
        !           588:  *             Initialize the reverse hash table implementation.
        !           589:  */
        !           590: 
        !           591: void
        !           592: ipc_hash_init(void)
        !           593: {
        !           594:        ipc_hash_index_t i;
        !           595: 
        !           596:        /* if not configured, initialize ipc_hash_global_size */
        !           597: 
        !           598:        if (ipc_hash_global_size == 0) {
        !           599:                ipc_hash_global_size = ipc_tree_entry_max >> 8;
        !           600:                if (ipc_hash_global_size < 32)
        !           601:                        ipc_hash_global_size = 32;
        !           602:        }
        !           603: 
        !           604:        /* make sure it is a power of two */
        !           605: 
        !           606:        ipc_hash_global_mask = ipc_hash_global_size - 1;
        !           607:        if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) {
        !           608:                unsigned int bit;
        !           609: 
        !           610:                /* round up to closest power of two */
        !           611: 
        !           612:                for (bit = 1;; bit <<= 1) {
        !           613:                        ipc_hash_global_mask |= bit;
        !           614:                        ipc_hash_global_size = ipc_hash_global_mask + 1;
        !           615: 
        !           616:                        if ((ipc_hash_global_size & ipc_hash_global_mask) == 0)
        !           617:                                break;
        !           618:                }
        !           619:        }
        !           620: 
        !           621:        /* allocate ipc_hash_global_table */
        !           622: 
        !           623:        ipc_hash_global_table = (ipc_hash_global_bucket_t)
        !           624:                kalloc((vm_size_t) (ipc_hash_global_size *
        !           625:                                    sizeof(struct ipc_hash_global_bucket)));
        !           626:        assert(ipc_hash_global_table != IHGB_NULL);
        !           627: 
        !           628:        /* and initialize it */
        !           629: 
        !           630:        for (i = 0; i < ipc_hash_global_size; i++) {
        !           631:                ipc_hash_global_bucket_t bucket;
        !           632: 
        !           633:                bucket = &ipc_hash_global_table[i];
        !           634:                ihgb_lock_init(bucket);
        !           635:                bucket->ihgb_head = ITE_NULL;
        !           636:        }
        !           637: }
        !           638: 
        !           639: #include <mach_ipc_debug.h>
        !           640: #if    MACH_IPC_DEBUG
        !           641: 
        !           642: #include <mach/kern_return.h>
        !           643: #include <mach_debug/hash_info.h>
        !           644: #include <vm/vm_map.h>
        !           645: #include <vm/vm_kern.h>
        !           646: #include <vm/vm_user.h>
        !           647: 
        !           648: /*
        !           649:  *     Routine:        ipc_hash_info
        !           650:  *     Purpose:
        !           651:  *             Return information about the global reverse hash table.
        !           652:  *             Fills the buffer with as much information as possible
        !           653:  *             and returns the desired size of the buffer.
        !           654:  *     Conditions:
        !           655:  *             Nothing locked.  The caller should provide
        !           656:  *             possibly-pageable memory.
        !           657:  */
        !           658: 
        !           659: unsigned int
        !           660: ipc_hash_info(
        !           661:        hash_info_bucket_t      *info,
        !           662:        unsigned int             count)
        !           663: {
        !           664:        ipc_hash_index_t i;
        !           665: 
        !           666:        if (ipc_hash_global_size < count)
        !           667:                count = ipc_hash_global_size;
        !           668: 
        !           669:        for (i = 0; i < count; i++) {
        !           670:                ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i];
        !           671:                unsigned int bucket_count = 0;
        !           672:                ipc_tree_entry_t entry;
        !           673: 
        !           674:                ihgb_lock(bucket);
        !           675:                for (entry = bucket->ihgb_head;
        !           676:                     entry != ITE_NULL;
        !           677:                     entry = entry->ite_next)
        !           678:                        bucket_count++;
        !           679:                ihgb_unlock(bucket);
        !           680: 
        !           681:                /* don't touch pageable memory while holding locks */
        !           682:                info[i].hib_count = bucket_count;
        !           683:        }
        !           684: 
        !           685:        return ipc_hash_global_size;
        !           686: }
        !           687: 
        !           688: #endif /* MACH_IPC_DEBUG */

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