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/lock.h>
  69 #include <kern/kalloc.h>
  70 #include <ipc/port.h>
  71 #include <ipc/ipc_space.h>
  72 #include <ipc/ipc_object.h>
  73 #include <ipc/ipc_entry.h>
  74 #include <ipc/ipc_hash.h>
  75 #include <ipc/ipc_init.h>
  76
  77 #include <mach_ipc_debug.h>
  78
  79 #if     MACH_IPC_DEBUG
  80 #include <mach/kern_return.h>
  81 #include <mach_debug/hash_info.h>
  82 #include <vm/vm_map.h>
  83 #include <vm/vm_kern.h>
  84 #endif  /* MACH_IPC_DEBUG */
  85
  86 /*
  87  * Forward declarations
  88  */
  89
  90 /* Delete an entry from the local reverse hash table */
  91 void ipc_hash_local_delete(
  92         ipc_space_t             space,
  93         ipc_object_t            obj,
  94         mach_port_index_t       index,
  95         ipc_entry_t             entry);
  96
  97 /*
  98  *      Routine:        ipc_hash_lookup
  99  *      Purpose:
 100  *              Converts (space, obj) -> (name, entry).
 101  *              Returns TRUE if an entry was found.
 102  *      Conditions:
 103  *              The space must be locked (read or write) throughout.
 104  */
 105
 106 boolean_t
 107 ipc_hash_lookup(
 108         ipc_space_t             space,
 109         ipc_object_t            obj,
 110         mach_port_name_t        *namep,
 111         ipc_entry_t             *entryp)
 112 {
 113         return ipc_hash_table_lookup(space->is_table, space->is_table_size, obj, namep, entryp);
 114 }
 115
 116 /*
 117  *      Routine:        ipc_hash_insert
 118  *      Purpose:
 119  *              Inserts an entry into the appropriate reverse hash table,
 120  *              so that ipc_hash_lookup will find it.
 121  *      Conditions:
 122  *              The space must be write-locked.
 123  */
 124
 125 void
 126 ipc_hash_insert(
 127         ipc_space_t             space,
 128         ipc_object_t            obj,
 129         mach_port_name_t        name,
 130         ipc_entry_t             entry)
 131 {
 132         mach_port_index_t index;
 133
 134         index = MACH_PORT_INDEX(name);
 135         ipc_hash_table_insert(space->is_table, space->is_table_size, obj, index, entry);
 136 }
 137
 138 /*
 139  *      Routine:        ipc_hash_delete
 140  *      Purpose:
 141  *              Deletes an entry from the appropriate reverse hash table.
 142  *      Conditions:
 143  *              The space must be write-locked.
 144  */
 145
 146 void
 147 ipc_hash_delete(
 148         ipc_space_t             space,
 149         ipc_object_t            obj,
 150         mach_port_name_t        name,
 151         ipc_entry_t             entry)
 152 {
 153         mach_port_index_t index;
 154
 155         index = MACH_PORT_INDEX(name);
 156         ipc_hash_table_delete(space->is_table, space->is_table_size, obj, index, entry);
 157 }
 158
 159 /*
 160  *      Each space has a local reverse hash table, which holds
 161  *      entries from the space's table.  In fact, the hash table
 162  *      just uses a field (ie_index) in the table itself.
 163  *
 164  *      The local hash table is an open-addressing hash table,
 165  *      which means that when a collision occurs, instead of
 166  *      throwing the entry into a bucket, the entry is rehashed
 167  *      to another position in the table.  In this case the rehash
 168  *      is very simple: linear probing (ie, just increment the position).
 169  *      This simple rehash makes deletions tractable (they're still a pain),
 170  *      but it means that collisions tend to build up into clumps.
 171  *
 172  *      Because at least one entry in the table (index 0) is always unused,
 173  *      there will always be room in the reverse hash table.  If a table
 174  *      with n slots gets completely full, the reverse hash table will
 175  *      have one giant clump of n-1 slots and one free slot somewhere.
 176  *      Because entries are only entered into the reverse table if they
 177  *      are pure send rights (not receive, send-once, port-set,
 178  *      or dead-name rights), and free entries of course aren't entered,
 179  *      I expect the reverse hash table won't get unreasonably full.
 180  *
 181  *      Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2,
 182  *      pp. 135-142.) may be desirable here.  They can dramatically help
 183  *      unsuccessful lookups.  But unsuccessful lookups are almost always
 184  *      followed by insertions, and those slow down somewhat.  They
 185  *      also can help deletions somewhat.  Successful lookups aren't affected.
 186  *      So possibly a small win; probably nothing significant.
 187  */
 188
 189 #define IH_TABLE_HASH(obj, size)                                \
 190                 ((mach_port_index_t)((((uintptr_t) (obj)) >> 6) % (size)))
 191
 192 /*
 193  *      Routine:        ipc_hash_table_lookup
 194  *      Purpose:
 195  *              Converts (table, obj) -> (name, entry).
 196  *      Conditions:
 197  *              Must have read consistency on the table.
 198  */
 199
 200 boolean_t
 201 ipc_hash_table_lookup(
 202         ipc_entry_t             table,
 203         ipc_entry_num_t         size,
 204         ipc_object_t            obj,
 205         mach_port_name_t        *namep,
 206         ipc_entry_t             *entryp)
 207 {
 208         mach_port_index_t hindex, index;
 209
 210         if (obj == IO_NULL) {
 211                 return FALSE;
 212         }
 213
 214         hindex = IH_TABLE_HASH(obj, size);
 215
 216         /*
 217          *      Ideally, table[hindex].ie_index is the name we want.
 218          *      However, must check ie_object to verify this,
 219          *      because collisions can happen.  In case of a collision,
 220          *      search farther along in the clump.
 221          */
 222
 223         while ((index = table[hindex].ie_index) != 0) {
 224                 ipc_entry_t entry;
 225
 226                 assert(index < size);
 227                 entry = &table[index];
 228                 if (entry->ie_object == obj) {
 229                         *entryp = entry;
 230                         *namep = MACH_PORT_MAKE(index,
 231                                                 IE_BITS_GEN(entry->ie_bits));
 232                         return TRUE;
 233                 }
 234
 235                 if (++hindex == size)
 236                         hindex = 0;
 237         }
 238
 239         return FALSE;
 240 }
 241
 242 /*
 243  *      Routine:        ipc_hash_table_insert
 244  *      Purpose:
 245  *              Inserts an entry into the space's reverse hash table.
 246  *      Conditions:
 247  *              The space must be write-locked.
 248  */
 249
 250 void
 251 ipc_hash_table_insert(
 252         ipc_entry_t                     table,
 253         ipc_entry_num_t                 size,
 254         ipc_object_t                    obj,
 255         mach_port_index_t               index,
 256         __assert_only ipc_entry_t       entry)
 257 {
 258         mach_port_index_t hindex;
 259
 260         assert(index != 0);
 261         assert(obj != IO_NULL);
 262
 263         hindex = IH_TABLE_HASH(obj, size);
 264
 265         assert(entry == &table[index]);
 266         assert(entry->ie_object == obj);
 267
 268         /*
 269          *      We want to insert at hindex, but there may be collisions.
 270          *      If a collision occurs, search for the end of the clump
 271          *      and insert there.
 272          */
 273
 274         while (table[hindex].ie_index != 0) {
 275                 if (++hindex == size)
 276                         hindex = 0;
 277         }
 278
 279         table[hindex].ie_index = index;
 280 }
 281
 282 /*
 283  *      Routine:        ipc_hash_table_delete
 284  *      Purpose:
 285  *              Deletes an entry from the table's reverse hash.
 286  *      Conditions:
 287  *              Exclusive access to the table.
 288  */
 289
 290 void
 291 ipc_hash_table_delete(
 292         ipc_entry_t                     table,
 293         ipc_entry_num_t                 size,
 294         ipc_object_t                    obj,
 295         mach_port_index_t               index,
 296         __assert_only ipc_entry_t       entry)
 297 {
 298         mach_port_index_t hindex, dindex;
 299
 300         assert(index != MACH_PORT_NULL);
 301         assert(obj != IO_NULL);
 302
 303         hindex = IH_TABLE_HASH(obj, size);
 304
 305         assert(entry == &table[index]);
 306         assert(entry->ie_object == obj);
 307
 308         /*
 309          *      First check we have the right hindex for this index.
 310          *      In case of collision, we have to search farther
 311          *      along in this clump.
 312          */
 313
 314         while (table[hindex].ie_index != index) {
 315                 if (++hindex == size)
 316                         hindex = 0;
 317         }
 318
 319         /*
 320          *      Now we want to set table[hindex].ie_index = 0.
 321          *      But if we aren't the last index in a clump,
 322          *      this might cause problems for lookups of objects
 323          *      farther along in the clump that are displaced
 324          *      due to collisions.  Searches for them would fail
 325          *      at hindex instead of succeeding.
 326          *
 327          *      So we must check the clump after hindex for objects
 328          *      that are so displaced, and move one up to the new hole.
 329          *
 330          *              hindex - index of new hole in the clump
 331          *              dindex - index we are checking for a displaced object
 332          *
 333          *      When we move a displaced object up into the hole,
 334          *      it creates a new hole, and we have to repeat the process
 335          *      until we get to the end of the clump.
 336          */
 337
 338         for (dindex = hindex; index != 0; hindex = dindex) {
 339                 for (;;) {
 340                         mach_port_index_t tindex;
 341                         ipc_object_t tobj;
 342
 343                         if (++dindex == size)
 344                                 dindex = 0;
 345                         assert(dindex != hindex);
 346
 347                         /* are we at the end of the clump? */
 348
 349                         index = table[dindex].ie_index;
 350                         if (index == 0)
 351                                 break;
 352
 353                         /* is this a displaced object? */
 354
 355                         tobj = table[index].ie_object;
 356                         assert(tobj != IO_NULL);
 357                         tindex = IH_TABLE_HASH(tobj, size);
 358
 359                         if ((dindex < hindex) ?
 360                             ((dindex < tindex) && (tindex <= hindex)) :
 361                             ((dindex < tindex) || (tindex <= hindex)))
 362                                 break;
 363                 }
 364
 365                 table[hindex].ie_index = index;
 366         }
 367 }
 368