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         assert(obj != IO_NULL);
 211
 212         hindex = IH_TABLE_HASH(obj, size);
 213
 214         /*
 215          *      Ideally, table[hindex].ie_index is the name we want.
 216          *      However, must check ie_object to verify this,
 217          *      because collisions can happen.  In case of a collision,
 218          *      search farther along in the clump.
 219          */
 220
 221         while ((index = table[hindex].ie_index) != 0) {
 222                 ipc_entry_t entry;
 223
 224                 assert(index < size);
 225                 entry = &table[index];
 226                 if (entry->ie_object == obj) {
 227                         *entryp = entry;
 228                         *namep = MACH_PORT_MAKE(index,
 229                                                 IE_BITS_GEN(entry->ie_bits));
 230                         return TRUE;
 231                 }
 232
 233                 if (++hindex == size)
 234                         hindex = 0;
 235         }
 236
 237         return FALSE;
 238 }
 239
 240 /*
 241  *      Routine:        ipc_hash_table_insert
 242  *      Purpose:
 243  *              Inserts an entry into the space's reverse hash table.
 244  *      Conditions:
 245  *              The space must be write-locked.
 246  */
 247
 248 void
 249 ipc_hash_table_insert(
 250         ipc_entry_t                     table,
 251         ipc_entry_num_t                 size,
 252         ipc_object_t                    obj,
 253         mach_port_index_t               index,
 254         __assert_only ipc_entry_t       entry)
 255 {
 256         mach_port_index_t hindex;
 257
 258         assert(index != 0);
 259         assert(obj != IO_NULL);
 260
 261         hindex = IH_TABLE_HASH(obj, size);
 262
 263         assert(entry == &table[index]);
 264         assert(entry->ie_object == obj);
 265
 266         /*
 267          *      We want to insert at hindex, but there may be collisions.
 268          *      If a collision occurs, search for the end of the clump
 269          *      and insert there.
 270          */
 271
 272         while (table[hindex].ie_index != 0) {
 273                 if (++hindex == size)
 274                         hindex = 0;
 275         }
 276
 277         table[hindex].ie_index = index;
 278 }
 279
 280 /*
 281  *      Routine:        ipc_hash_table_delete
 282  *      Purpose:
 283  *              Deletes an entry from the table's reverse hash.
 284  *      Conditions:
 285  *              Exclusive access to the table.
 286  */
 287
 288 void
 289 ipc_hash_table_delete(
 290         ipc_entry_t                     table,
 291         ipc_entry_num_t                 size,
 292         ipc_object_t                    obj,
 293         mach_port_index_t               index,
 294         __assert_only ipc_entry_t       entry)
 295 {
 296         mach_port_index_t hindex, dindex;
 297
 298         assert(index != MACH_PORT_NULL);
 299         assert(obj != IO_NULL);
 300
 301         hindex = IH_TABLE_HASH(obj, size);
 302
 303         assert(entry == &table[index]);
 304         assert(entry->ie_object == obj);
 305
 306         /*
 307          *      First check we have the right hindex for this index.
 308          *      In case of collision, we have to search farther
 309          *      along in this clump.
 310          */
 311
 312         while (table[hindex].ie_index != index) {
 313                 if (++hindex == size)
 314                         hindex = 0;
 315         }
 316
 317         /*
 318          *      Now we want to set table[hindex].ie_index = 0.
 319          *      But if we aren't the last index in a clump,
 320          *      this might cause problems for lookups of objects
 321          *      farther along in the clump that are displaced
 322          *      due to collisions.  Searches for them would fail
 323          *      at hindex instead of succeeding.
 324          *
 325          *      So we must check the clump after hindex for objects
 326          *      that are so displaced, and move one up to the new hole.
 327          *
 328          *              hindex - index of new hole in the clump
 329          *              dindex - index we are checking for a displaced object
 330          *
 331          *      When we move a displaced object up into the hole,
 332          *      it creates a new hole, and we have to repeat the process
 333          *      until we get to the end of the clump.
 334          */
 335
 336         for (dindex = hindex; index != 0; hindex = dindex) {
 337                 for (;;) {
 338                         mach_port_index_t tindex;
 339                         ipc_object_t tobj;
 340
 341                         if (++dindex == size)
 342                                 dindex = 0;
 343                         assert(dindex != hindex);
 344
 345                         /* are we at the end of the clump? */
 346
 347                         index = table[dindex].ie_index;
 348                         if (index == 0)
 349                                 break;
 350
 351                         /* is this a displaced object? */
 352
 353                         tobj = table[index].ie_object;
 354                         assert(tobj != IO_NULL);
 355                         tindex = IH_TABLE_HASH(tobj, size);
 356
 357                         if ((dindex < hindex) ?
 358                             ((dindex < tindex) && (tindex <= hindex)) :
 359                             ((dindex < tindex) || (tindex <= hindex)))
 360                                 break;
 361                 }
 362
 363                 table[hindex].ie_index = index;
 364         }
 365 }
 366