xnu-3248.60.10.tar.gz

[apple/xnu.git] / osfmk / ipc / ipc_hash.c

diff --git a/osfmk/ipc/ipc_hash.c b/osfmk/ipc/ipc_hash.c
index 84450169538faa269790b34db7ecf1bf0da01c9c..a8f79a647f41074e51c57c7bf9dfdbeb03a0d7e5 100644 (file)
--- a/osfmk/ipc/ipc_hash.c
+++ b/osfmk/ipc/ipc_hash.c
@@ -1,23 +1,29 @@
 /*
 /*

- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.

  *
  *

- * @APPLE_LICENSE_HEADER_START@
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_START@

  * 
  * 

- * The contents of this file constitute Original Code as defined in and
- * are subject to the Apple Public Source License Version 1.1 (the
- * "License").  You may not use this file except in compliance with the
- * License.  Please obtain a copy of the License at
- * http://www.apple.com/publicsource and read it before using this file.
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. The rights granted to you under the License
+ * may not be used to create, or enable the creation or redistribution of,
+ * unlawful or unlicensed copies of an Apple operating system, or to
+ * circumvent, violate, or enable the circumvention or violation of, any
+ * terms of an Apple operating system software license agreement.

  * 
  * 

- * This Original Code and all software distributed under the License are
- * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this file.
+ * 
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER

  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,

- * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
- * License for the specific language governing rights and limitations
- * under the License.
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.

  * 
  * 

- * @APPLE_LICENSE_HEADER_END@
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_END@

  */
 /*
  * @OSF_COPYRIGHT@
  */
 /*
  * @OSF_COPYRIGHT@


@@ -59,7 +65,6 @@
 
 #include <mach/boolean.h>
 #include <mach/port.h>
 
 #include <mach/boolean.h>
 #include <mach/port.h>

-#include <kern/lock.h>

 #include <kern/kalloc.h>
 #include <ipc/port.h>
 #include <ipc/ipc_space.h>
 #include <kern/kalloc.h>
 #include <ipc/port.h>
 #include <ipc/ipc_space.h>


@@ -81,20 +86,6 @@
  * Forward declarations 
  */
 
  * Forward declarations 
  */
 

-/* Lookup (space, obj) in global hash table */
-boolean_t ipc_hash_global_lookup(
-       ipc_space_t             space,
-       ipc_object_t            obj,
-       mach_port_name_t        *namep,
-       ipc_tree_entry_t        *entryp);
-
-/* Insert an entry into the global reverse hash table */
-void ipc_hash_global_insert(
-       ipc_space_t             space,
-       ipc_object_t            obj,
-       mach_port_name_t        name,
-       ipc_tree_entry_t        entry);
-

 /* Delete an entry from the local reverse hash table */
 void ipc_hash_local_delete(
        ipc_space_t             space,
 /* Delete an entry from the local reverse hash table */
 void ipc_hash_local_delete(
        ipc_space_t             space,


@@ -118,16 +109,7 @@ ipc_hash_lookup(
        mach_port_name_t        *namep,
        ipc_entry_t             *entryp)
 {
        mach_port_name_t        *namep,
        ipc_entry_t             *entryp)
 {

-       boolean_t       rv;
-
-       rv = ipc_hash_local_lookup(space, obj, namep, entryp);
-       if (!rv) {
-               assert(!is_fast_space(space) || space->is_tree_hash == 0);
-               if (space->is_tree_hash > 0)
-                       rv = ipc_hash_global_lookup(space, obj, namep,
-                               (ipc_tree_entry_t *) entryp);
-       }
-       return (rv);
+       return ipc_hash_table_lookup(space->is_table, space->is_table_size, obj, namep, entryp);

 }
 
 /*
 }
 
 /*


@@ -149,14 +131,7 @@ ipc_hash_insert(
        mach_port_index_t index;
 
        index = MACH_PORT_INDEX(name);
        mach_port_index_t index;
 
        index = MACH_PORT_INDEX(name);

-       if ((index < space->is_table_size) &&
-           (entry == &space->is_table[index]))
-               ipc_hash_local_insert(space, obj, index, entry);
-       else {
-               assert(!is_fast_space(space));
-               ipc_hash_global_insert(space, obj, name,
-                                      (ipc_tree_entry_t) entry);
-       }
+       ipc_hash_table_insert(space->is_table, space->is_table_size, obj, index, entry);

 }
 
 /*
 }
 
 /*


@@ -177,189 +152,7 @@ ipc_hash_delete(
        mach_port_index_t index;
 
        index = MACH_PORT_INDEX(name);
        mach_port_index_t index;
 
        index = MACH_PORT_INDEX(name);

-       if ((index < space->is_table_size) &&
-           (entry == &space->is_table[index]))
-               ipc_hash_local_delete(space, obj, index, entry);
-       else {
-               assert(!is_fast_space(space));
-               ipc_hash_global_delete(space, obj, name,
-                                      (ipc_tree_entry_t) entry);
-       }
-}
-
-/*
- *     The global reverse hash table holds splay tree entries.
- *     It is a simple open-chaining hash table with singly-linked buckets.
- *     Each bucket is locked separately, with an exclusive lock.
- *     Within each bucket, move-to-front is used.
- */
-
-typedef natural_t ipc_hash_index_t;
-
-ipc_hash_index_t ipc_hash_global_size;
-ipc_hash_index_t ipc_hash_global_mask;
-
-#define IH_GLOBAL_HASH(space, obj)                                     \
-       (((((ipc_hash_index_t) ((vm_offset_t)space)) >> 4) +            \
-         (((ipc_hash_index_t) ((vm_offset_t)obj)) >> 6)) &             \
-        ipc_hash_global_mask)
-
-typedef struct ipc_hash_global_bucket {
-       decl_mutex_data(,       ihgb_lock_data)
-       ipc_tree_entry_t        ihgb_head;
-} *ipc_hash_global_bucket_t;
-
-#define        IHGB_NULL       ((ipc_hash_global_bucket_t) 0)
-
-#define        ihgb_lock_init(ihgb)    mutex_init(&(ihgb)->ihgb_lock_data, \
-                                          ETAP_IPC_IHGB)
-#define        ihgb_lock(ihgb)         mutex_lock(&(ihgb)->ihgb_lock_data)
-#define        ihgb_unlock(ihgb)       mutex_unlock(&(ihgb)->ihgb_lock_data)
-
-ipc_hash_global_bucket_t ipc_hash_global_table;
-
-/*
- *     Routine:        ipc_hash_global_lookup
- *     Purpose:
- *             Converts (space, obj) -> (name, entry).
- *             Looks in the global table, for splay tree entries.
- *             Returns TRUE if an entry was found.
- *     Conditions:
- *             The space must be locked (read or write) throughout.
- */
-
-boolean_t
-ipc_hash_global_lookup(
-       ipc_space_t                     space,
-       ipc_object_t                    obj,
-       mach_port_name_t                *namep,
-       ipc_tree_entry_t                *entryp)
-{
-       ipc_hash_global_bucket_t bucket;
-       ipc_tree_entry_t this, *last;
-
-       assert(space != IS_NULL);
-       assert(obj != IO_NULL);
-
-       assert(!is_fast_space(space));
-       bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
-       ihgb_lock(bucket);
-
-       if ((this = bucket->ihgb_head) != ITE_NULL) {
-               if ((this->ite_object == obj) &&
-                   (this->ite_space == space)) {
-                       /* found it at front; no need to move */
-
-                       *namep = this->ite_name;
-                       *entryp = this;
-               } else for (last = &this->ite_next;
-                           (this = *last) != ITE_NULL;
-                           last = &this->ite_next) {
-                       if ((this->ite_object == obj) &&
-                           (this->ite_space == space)) {
-                               /* found it; move to front */
-
-                               *last = this->ite_next;
-                               this->ite_next = bucket->ihgb_head;
-                               bucket->ihgb_head = this;
-
-                               *namep = this->ite_name;
-                               *entryp = this;
-                               break;
-                       }
-               }
-       }
-
-       ihgb_unlock(bucket);
-       return this != ITE_NULL;
-}
-
-/*
- *     Routine:        ipc_hash_global_insert
- *     Purpose:
- *             Inserts an entry into the global reverse hash table.
- *     Conditions:
- *             The space must be write-locked.
- */
-
-void
-ipc_hash_global_insert(
-       ipc_space_t                     space,
-       ipc_object_t                    obj,
-       mach_port_name_t                name,
-       ipc_tree_entry_t                entry)
-{
-       ipc_hash_global_bucket_t bucket;
-
-
-       assert(!is_fast_space(space));
-
-
-       assert(entry->ite_name == name);
-       assert(space != IS_NULL);
-       assert(entry->ite_space == space);
-       assert(obj != IO_NULL);
-       assert(entry->ite_object == obj);
-
-       space->is_tree_hash++;
-       assert(space->is_tree_hash <= space->is_tree_total);
-
-       bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
-       ihgb_lock(bucket);
-
-       /* insert at front of bucket */
-
-       entry->ite_next = bucket->ihgb_head;
-       bucket->ihgb_head = entry;
-
-       ihgb_unlock(bucket);
-}
-
-/*
- *     Routine:        ipc_hash_global_delete
- *     Purpose:
- *             Deletes an entry from the global reverse hash table.
- *     Conditions:
- *             The space must be write-locked.
- */
-
-void
-ipc_hash_global_delete(
-       ipc_space_t                     space,
-       ipc_object_t                    obj,
-       mach_port_name_t                name,
-       ipc_tree_entry_t                entry)
-{
-       ipc_hash_global_bucket_t bucket;
-       ipc_tree_entry_t this, *last;
-
-       assert(!is_fast_space(space));
-
-       assert(entry->ite_name == name);
-       assert(space != IS_NULL);
-       assert(entry->ite_space == space);
-       assert(obj != IO_NULL);
-       assert(entry->ite_object == obj);
-
-       assert(space->is_tree_hash > 0);
-       space->is_tree_hash--;
-
-       bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
-       ihgb_lock(bucket);
-
-       for (last = &bucket->ihgb_head;
-            (this = *last) != ITE_NULL;
-            last = &this->ite_next) {
-               if (this == entry) {
-                       /* found it; remove from bucket */
-
-                       *last = this->ite_next;
-                       break;
-               }
-       }
-       assert(this != ITE_NULL);
-
-       ihgb_unlock(bucket);
+       ipc_hash_table_delete(space->is_table, space->is_table_size, obj, index, entry);

 }
 
 /*
 }
 
 /*


@@ -392,36 +185,32 @@ ipc_hash_global_delete(
  *     So possibly a small win; probably nothing significant.
  */
 
  *     So possibly a small win; probably nothing significant.
  */
 

-#define        IH_LOCAL_HASH(obj, size)                                \
-               ((((mach_port_index_t) (obj)) >> 6) % (size))
+#define        IH_TABLE_HASH(obj, size)                                \
+               ((mach_port_index_t)((((uintptr_t) (obj)) >> 6) % (size)))

 
 /*
 
 /*

- *     Routine:        ipc_hash_local_lookup
+ *     Routine:        ipc_hash_table_lookup

  *     Purpose:
  *     Purpose:

- *             Converts (space, obj) -> (name, entry).
- *             Looks in the space's local table, for table entries.
- *             Returns TRUE if an entry was found.
+ *             Converts (table, obj) -> (name, entry).

  *     Conditions:
  *     Conditions:

- *             The space must be locked (read or write) throughout.
+ *             Must have read consistency on the table.

  */
 
 boolean_t
  */
 
 boolean_t

-ipc_hash_local_lookup(
-       ipc_space_t             space,
+ipc_hash_table_lookup(
+       ipc_entry_t             table,
+       ipc_entry_num_t         size,

        ipc_object_t            obj,
        mach_port_name_t        *namep,
        ipc_entry_t             *entryp)
 {
        ipc_object_t            obj,
        mach_port_name_t        *namep,
        ipc_entry_t             *entryp)
 {

-       ipc_entry_t table;
-       ipc_entry_num_t size;

        mach_port_index_t hindex, index;
 
        mach_port_index_t hindex, index;
 

-       assert(space != IS_NULL);
-       assert(obj != IO_NULL);
+       if (obj == IO_NULL) {
+               return FALSE;
+       }

 
 

-       table = space->is_table;
-       size = space->is_table_size;
-       hindex = IH_LOCAL_HASH(obj, size);
+       hindex = IH_TABLE_HASH(obj, size);

 
        /*
         *      Ideally, table[hindex].ie_index is the name we want.
 
        /*
         *      Ideally, table[hindex].ie_index is the name we want.


@@ -431,8 +220,10 @@ ipc_hash_local_lookup(
         */
 
        while ((index = table[hindex].ie_index) != 0) {
         */
 
        while ((index = table[hindex].ie_index) != 0) {

-               ipc_entry_t entry = &table[index];
+               ipc_entry_t entry;

 
 

+               assert(index < size);
+               entry = &table[index];

                if (entry->ie_object == obj) {
                        *entryp = entry;
                        *namep = MACH_PORT_MAKE(index,
                if (entry->ie_object == obj) {
                        *entryp = entry;
                        *namep = MACH_PORT_MAKE(index,


@@ -448,7 +239,7 @@ ipc_hash_local_lookup(
 }
 
 /*
 }
 
 /*

- *     Routine:        ipc_hash_local_insert
+ *     Routine:        ipc_hash_table_insert

  *     Purpose:
  *             Inserts an entry into the space's reverse hash table.
  *     Conditions:
  *     Purpose:
  *             Inserts an entry into the space's reverse hash table.
  *     Conditions:


@@ -456,23 +247,19 @@ ipc_hash_local_lookup(
  */
 
 void
  */
 
 void

-ipc_hash_local_insert(
-       ipc_space_t             space,
-       ipc_object_t            obj,
-       mach_port_index_t       index,
-       ipc_entry_t             entry)
+ipc_hash_table_insert(
+       ipc_entry_t                     table,
+       ipc_entry_num_t                 size,
+       ipc_object_t                    obj,
+       mach_port_index_t               index,
+       __assert_only ipc_entry_t       entry)

 {
 {

-       ipc_entry_t table;
-       ipc_entry_num_t size;

        mach_port_index_t hindex;
 
        assert(index != 0);
        mach_port_index_t hindex;
 
        assert(index != 0);

-       assert(space != IS_NULL);

        assert(obj != IO_NULL);
 
        assert(obj != IO_NULL);
 

-       table = space->is_table;
-       size = space->is_table_size;
-       hindex = IH_LOCAL_HASH(obj, size);
+       hindex = IH_TABLE_HASH(obj, size);

 
        assert(entry == &table[index]);
        assert(entry->ie_object == obj);
 
        assert(entry == &table[index]);
        assert(entry->ie_object == obj);


@@ -492,31 +279,27 @@ ipc_hash_local_insert(
 }
 
 /*
 }
 
 /*

- *     Routine:        ipc_hash_local_delete
+ *     Routine:        ipc_hash_table_delete

  *     Purpose:
  *     Purpose:

- *             Deletes an entry from the space's reverse hash table.
+ *             Deletes an entry from the table's reverse hash.

  *     Conditions:
  *     Conditions:

- *             The space must be write-locked.
+ *             Exclusive access to the table.

  */
 
 void
  */
 
 void

-ipc_hash_local_delete(
-       ipc_space_t             space,
-       ipc_object_t            obj,
-       mach_port_index_t       index,
-       ipc_entry_t             entry)
+ipc_hash_table_delete(
+       ipc_entry_t                     table,
+       ipc_entry_num_t                 size,
+       ipc_object_t                    obj,
+       mach_port_index_t               index,
+       __assert_only ipc_entry_t       entry)

 {
 {

-       ipc_entry_t table;
-       ipc_entry_num_t size;

        mach_port_index_t hindex, dindex;
 
        assert(index != MACH_PORT_NULL);
        mach_port_index_t hindex, dindex;
 
        assert(index != MACH_PORT_NULL);

-       assert(space != IS_NULL);

        assert(obj != IO_NULL);
 
        assert(obj != IO_NULL);
 

-       table = space->is_table;
-       size = space->is_table_size;
-       hindex = IH_LOCAL_HASH(obj, size);
+       hindex = IH_TABLE_HASH(obj, size);

 
        assert(entry == &table[index]);
        assert(entry->ie_object == obj);
 
        assert(entry == &table[index]);
        assert(entry->ie_object == obj);


@@ -570,7 +353,7 @@ ipc_hash_local_delete(
 
                        tobj = table[index].ie_object;
                        assert(tobj != IO_NULL);
 
                        tobj = table[index].ie_object;
                        assert(tobj != IO_NULL);

-                       tindex = IH_LOCAL_HASH(tobj, size);
+                       tindex = IH_TABLE_HASH(tobj, size);

 
                        if ((dindex < hindex) ?
                            ((dindex < tindex) && (tindex <= hindex)) :
 
                        if ((dindex < hindex) ?
                            ((dindex < tindex) && (tindex <= hindex)) :


@@ -582,101 +365,3 @@ ipc_hash_local_delete(
        }
 }
 
        }
 }
 

-/*
- *     Routine:        ipc_hash_init
- *     Purpose:
- *             Initialize the reverse hash table implementation.
- */
-
-void
-ipc_hash_init(void)
-{
-       ipc_hash_index_t i;
-
-       /* if not configured, initialize ipc_hash_global_size */
-
-       if (ipc_hash_global_size == 0) {
-               ipc_hash_global_size = ipc_tree_entry_max >> 8;
-               if (ipc_hash_global_size < 32)
-                       ipc_hash_global_size = 32;
-       }
-
-       /* make sure it is a power of two */
-
-       ipc_hash_global_mask = ipc_hash_global_size - 1;
-       if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) {
-               natural_t bit;
-
-               /* round up to closest power of two */
-
-               for (bit = 1;; bit <<= 1) {
-                       ipc_hash_global_mask |= bit;
-                       ipc_hash_global_size = ipc_hash_global_mask + 1;
-
-                       if ((ipc_hash_global_size & ipc_hash_global_mask) == 0)
-                               break;
-               }
-       }
-
-       /* allocate ipc_hash_global_table */
-
-       ipc_hash_global_table = (ipc_hash_global_bucket_t)
-               kalloc((vm_size_t) (ipc_hash_global_size *
-                                   sizeof(struct ipc_hash_global_bucket)));
-       assert(ipc_hash_global_table != IHGB_NULL);
-
-       /* and initialize it */
-
-       for (i = 0; i < ipc_hash_global_size; i++) {
-               ipc_hash_global_bucket_t bucket;
-
-               bucket = &ipc_hash_global_table[i];
-               ihgb_lock_init(bucket);
-               bucket->ihgb_head = ITE_NULL;
-       }
-}
-
-#if    MACH_IPC_DEBUG
-
-/*
- *     Routine:        ipc_hash_info
- *     Purpose:
- *             Return information about the global reverse hash table.
- *             Fills the buffer with as much information as possible
- *             and returns the desired size of the buffer.
- *     Conditions:
- *             Nothing locked.  The caller should provide
- *             possibly-pageable memory.
- */
-
-
-ipc_hash_index_t
-ipc_hash_info(
-       hash_info_bucket_t      *info,
-       mach_msg_type_number_t count)
-{
-       ipc_hash_index_t i;
-
-       if (ipc_hash_global_size < count)
-               count = ipc_hash_global_size;
-
-       for (i = 0; i < count; i++) {
-               ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i];
-               unsigned int bucket_count = 0;
-               ipc_tree_entry_t entry;
-
-               ihgb_lock(bucket);
-               for (entry = bucket->ihgb_head;
-                    entry != ITE_NULL;
-                    entry = entry->ite_next)
-                       bucket_count++;
-               ihgb_unlock(bucket);
-
-               /* don't touch pageable memory while holding locks */
-               info[i].hib_count = bucket_count;
-       }
-
-       return ipc_hash_global_size;
-}
-
-#endif /* MACH_IPC_DEBUG */