osfmk/ipc/ipc_hash.c

   1 /*
   2  * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29  * @OSF_COPYRIGHT@
  30  */
  31 /*
  32  * Mach Operating System
  33  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
  34  * All Rights Reserved.
  35  *
  36  * Permission to use, copy, modify and distribute this software and its
  37  * documentation is hereby granted, provided that both the copyright
  38  * notice and this permission notice appear in all copies of the
  39  * software, derivative works or modified versions, and any portions
  40  * thereof, and that both notices appear in supporting documentation.
  41  *
  42  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  43  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  44  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  45  *
  46  * Carnegie Mellon requests users of this software to return to
  47  *
  48  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  49  *  School of Computer Science
  50  *  Carnegie Mellon University
  51  *  Pittsburgh PA 15213-3890
  52  *
  53  * any improvements or extensions that they make and grant Carnegie Mellon
  54  * the rights to redistribute these changes.
  55  */
  56 /*
  57  */
  58 /*
  59  *      File:   ipc/ipc_hash.c
  60  *      Author: Rich Draves
  61  *      Date:   1989
  62  *
  63  *      Entry hash table operations.
  64  */
  65
  66 #include <mach/boolean.h>
  67 #include <mach/port.h>
  68 #include <kern/kalloc.h>
  69 #include <ipc/port.h>
  70 #include <ipc/ipc_space.h>
  71 #include <ipc/ipc_object.h>
  72 #include <ipc/ipc_entry.h>
  73 #include <ipc/ipc_hash.h>
  74 #include <ipc/ipc_init.h>
  75
  76 #include <mach_ipc_debug.h>
  77
  78 #if     MACH_IPC_DEBUG
  79 #include <mach/kern_return.h>
  80 #include <mach_debug/hash_info.h>
  81 #include <vm/vm_map.h>
  82 #include <vm/vm_kern.h>
  83 #endif  /* MACH_IPC_DEBUG */
  84
  85 /*
  86  * Forward declarations
  87  */
  88
  89 /* Delete an entry from the local reverse hash table */
  90 void ipc_hash_local_delete(
  91         ipc_space_t             space,
  92         ipc_object_t            obj,
  93         mach_port_index_t       index,
  94         ipc_entry_t             entry);
  95
  96 /*
  97  *      Routine:        ipc_hash_lookup
  98  *      Purpose:
  99  *              Converts (space, obj) -> (name, entry).
 100  *              Returns TRUE if an entry was found.
 101  *      Conditions:
 102  *              The space must be locked (read or write) throughout.
 103  */
 104
 105 boolean_t
 106 ipc_hash_lookup(
 107         ipc_space_t             space,
 108         ipc_object_t            obj,
 109         mach_port_name_t        *namep,
 110         ipc_entry_t             *entryp)
 111 {
 112         return ipc_hash_table_lookup(space->is_table, space->is_table_size, obj, namep, entryp);
 113 }
 114
 115 /*
 116  *      Routine:        ipc_hash_insert
 117  *      Purpose:
 118  *              Inserts an entry into the appropriate reverse hash table,
 119  *              so that ipc_hash_lookup will find it.
 120  *      Conditions:
 121  *              The space must be write-locked.
 122  */
 123
 124 void
 125 ipc_hash_insert(
 126         ipc_space_t             space,
 127         ipc_object_t            obj,
 128         mach_port_name_t        name,
 129         ipc_entry_t             entry)
 130 {
 131         mach_port_index_t index;
 132
 133         index = MACH_PORT_INDEX(name);
 134         ipc_hash_table_insert(space->is_table, space->is_table_size, obj, index, entry);
 135 }
 136
 137 /*
 138  *      Routine:        ipc_hash_delete
 139  *      Purpose:
 140  *              Deletes an entry from the appropriate reverse hash table.
 141  *      Conditions:
 142  *              The space must be write-locked.
 143  */
 144
 145 void
 146 ipc_hash_delete(
 147         ipc_space_t             space,
 148         ipc_object_t            obj,
 149         mach_port_name_t        name,
 150         ipc_entry_t             entry)
 151 {
 152         mach_port_index_t index;
 153
 154         index = MACH_PORT_INDEX(name);
 155         ipc_hash_table_delete(space->is_table, space->is_table_size, obj, index, entry);
 156 }
 157
 158 /*
 159  *      Each space has a local reverse hash table, which holds
 160  *      entries from the space's table.  In fact, the hash table
 161  *      just uses a field (ie_index) in the table itself.
 162  *
 163  *      The local hash table is an open-addressing hash table,
 164  *      which means that when a collision occurs, instead of
 165  *      throwing the entry into a bucket, the entry is rehashed
 166  *      to another position in the table.  In this case the rehash
 167  *      is very simple: linear probing (ie, just increment the position).
 168  *      This simple rehash makes deletions tractable (they're still a pain),
 169  *      but it means that collisions tend to build up into clumps.
 170  *
 171  *      Because at least one entry in the table (index 0) is always unused,
 172  *      there will always be room in the reverse hash table.  If a table
 173  *      with n slots gets completely full, the reverse hash table will
 174  *      have one giant clump of n-1 slots and one free slot somewhere.
 175  *      Because entries are only entered into the reverse table if they
 176  *      are pure send rights (not receive, send-once, port-set,
 177  *      or dead-name rights), and free entries of course aren't entered,
 178  *      I expect the reverse hash table won't get unreasonably full.
 179  *
 180  *      Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2,
 181  *      pp. 135-142.) may be desirable here.  They can dramatically help
 182  *      unsuccessful lookups.  But unsuccessful lookups are almost always
 183  *      followed by insertions, and those slow down somewhat.  They
 184  *      also can help deletions somewhat.  Successful lookups aren't affected.
 185  *      So possibly a small win; probably nothing significant.
 186  */
 187
 188 #define IH_TABLE_HASH(obj, size)                                \
 189                 ((mach_port_index_t)((((uintptr_t) (obj)) >> 6) % (size)))
 190
 191 /*
 192  *      Routine:        ipc_hash_table_lookup
 193  *      Purpose:
 194  *              Converts (table, obj) -> (name, entry).
 195  *      Conditions:
 196  *              Must have read consistency on the table.
 197  */
 198
 199 boolean_t
 200 ipc_hash_table_lookup(
 201         ipc_entry_t             table,
 202         ipc_entry_num_t         size,
 203         ipc_object_t            obj,
 204         mach_port_name_t        *namep,
 205         ipc_entry_t             *entryp)
 206 {
 207         mach_port_index_t hindex, index;
 208
 209         if (obj == IO_NULL) {
 210                 return FALSE;
 211         }
 212
 213         hindex = IH_TABLE_HASH(obj, size);
 214
 215         /*
 216          *      Ideally, table[hindex].ie_index is the name we want.
 217          *      However, must check ie_object to verify this,
 218          *      because collisions can happen.  In case of a collision,
 219          *      search farther along in the clump.
 220          */
 221
 222         while ((index = table[hindex].ie_index) != 0) {
 223                 ipc_entry_t entry;
 224
 225                 assert(index < size);
 226                 entry = &table[index];
 227                 if (entry->ie_object == obj) {
 228                         *entryp = entry;
 229                         *namep = MACH_PORT_MAKE(index,
 230                                                 IE_BITS_GEN(entry->ie_bits));
 231                         return TRUE;
 232                 }
 233
 234                 if (++hindex == size)
 235                         hindex = 0;
 236         }
 237
 238         return FALSE;
 239 }
 240
 241 /*
 242  *      Routine:        ipc_hash_table_insert
 243  *      Purpose:
 244  *              Inserts an entry into the space's reverse hash table.
 245  *      Conditions:
 246  *              The space must be write-locked.
 247  */
 248
 249 void
 250 ipc_hash_table_insert(
 251         ipc_entry_t                     table,
 252         ipc_entry_num_t                 size,
 253         ipc_object_t                    obj,
 254         mach_port_index_t               index,
 255         __assert_only ipc_entry_t       entry)
 256 {
 257         mach_port_index_t hindex;
 258
 259         assert(index != 0);
 260         assert(obj != IO_NULL);
 261
 262         hindex = IH_TABLE_HASH(obj, size);
 263
 264         assert(entry == &table[index]);
 265         assert(entry->ie_object == obj);
 266
 267         /*
 268          *      We want to insert at hindex, but there may be collisions.
 269          *      If a collision occurs, search for the end of the clump
 270          *      and insert there.
 271          */
 272
 273         while (table[hindex].ie_index != 0) {
 274                 if (++hindex == size)
 275                         hindex = 0;
 276         }
 277
 278         table[hindex].ie_index = index;
 279 }
 280
 281 /*
 282  *      Routine:        ipc_hash_table_delete
 283  *      Purpose:
 284  *              Deletes an entry from the table's reverse hash.
 285  *      Conditions:
 286  *              Exclusive access to the table.
 287  */
 288
 289 void
 290 ipc_hash_table_delete(
 291         ipc_entry_t                     table,
 292         ipc_entry_num_t                 size,
 293         ipc_object_t                    obj,
 294         mach_port_index_t               index,
 295         __assert_only ipc_entry_t       entry)
 296 {
 297         mach_port_index_t hindex, dindex;
 298
 299         assert(index != MACH_PORT_NULL);
 300         assert(obj != IO_NULL);
 301
 302         hindex = IH_TABLE_HASH(obj, size);
 303
 304         assert(entry == &table[index]);
 305         assert(entry->ie_object == obj);
 306
 307         /*
 308          *      First check we have the right hindex for this index.
 309          *      In case of collision, we have to search farther
 310          *      along in this clump.
 311          */
 312
 313         while (table[hindex].ie_index != index) {
 314                 if (++hindex == size)
 315                         hindex = 0;
 316         }
 317
 318         /*
 319          *      Now we want to set table[hindex].ie_index = 0.
 320          *      But if we aren't the last index in a clump,
 321          *      this might cause problems for lookups of objects
 322          *      farther along in the clump that are displaced
 323          *      due to collisions.  Searches for them would fail
 324          *      at hindex instead of succeeding.
 325          *
 326          *      So we must check the clump after hindex for objects
 327          *      that are so displaced, and move one up to the new hole.
 328          *
 329          *              hindex - index of new hole in the clump
 330          *              dindex - index we are checking for a displaced object
 331          *
 332          *      When we move a displaced object up into the hole,
 333          *      it creates a new hole, and we have to repeat the process
 334          *      until we get to the end of the clump.
 335          */
 336
 337         for (dindex = hindex; index != 0; hindex = dindex) {
 338                 for (;;) {
 339                         mach_port_index_t tindex;
 340                         ipc_object_t tobj;
 341
 342                         if (++dindex == size)
 343                                 dindex = 0;
 344                         assert(dindex != hindex);
 345
 346                         /* are we at the end of the clump? */
 347
 348                         index = table[dindex].ie_index;
 349                         if (index == 0)
 350                                 break;
 351
 352                         /* is this a displaced object? */
 353
 354                         tobj = table[index].ie_object;
 355                         assert(tobj != IO_NULL);
 356                         tindex = IH_TABLE_HASH(tobj, size);
 357
 358                         if ((dindex < hindex) ?
 359                             ((dindex < tindex) && (tindex <= hindex)) :
 360                             ((dindex < tindex) || (tindex <= hindex)))
 361                                 break;
 362                 }
 363
 364                 table[hindex].ie_index = index;
 365         }
 366 }
 367