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 #include <os/hash.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         space->is_table_hashed++;
 136         ipc_hash_table_insert(space->is_table, space->is_table_size, obj, index, entry);
 137 }
 138
 139 /*
 140  *      Routine:        ipc_hash_delete
 141  *      Purpose:
 142  *              Deletes an entry from the appropriate reverse hash table.
 143  *      Conditions:
 144  *              The space must be write-locked.
 145  */
 146
 147 void
 148 ipc_hash_delete(
 149         ipc_space_t             space,
 150         ipc_object_t            obj,
 151         mach_port_name_t        name,
 152         ipc_entry_t             entry)
 153 {
 154         mach_port_index_t index;
 155
 156         index = MACH_PORT_INDEX(name);
 157         space->is_table_hashed--;
 158         ipc_hash_table_delete(space->is_table, space->is_table_size, obj, index, entry);
 159 }
 160
 161 /*
 162  *      Each space has a local reverse hash table, which holds
 163  *      entries from the space's table.  In fact, the hash table
 164  *      just uses a field (ie_index) in the table itself.
 165  *
 166  *      The local hash table is an open-addressing hash table,
 167  *      which means that when a collision occurs, instead of
 168  *      throwing the entry into a bucket, the entry is rehashed
 169  *      to another position in the table.  In this case the rehash
 170  *      is very simple: linear probing (ie, just increment the position).
 171  *      This simple rehash makes deletions tractable (they're still a pain),
 172  *      but it means that collisions tend to build up into clumps.
 173  *
 174  *      Because at least one entry in the table (index 0) is always unused,
 175  *      there will always be room in the reverse hash table.  If a table
 176  *      with n slots gets completely full, the reverse hash table will
 177  *      have one giant clump of n-1 slots and one free slot somewhere.
 178  *      Because entries are only entered into the reverse table if they
 179  *      are pure send rights (not receive, send-once, port-set,
 180  *      or dead-name rights), and free entries of course aren't entered,
 181  *      I expect the reverse hash table won't get unreasonably full.
 182  *
 183  *      Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2,
 184  *      pp. 135-142.) may be desirable here.  They can dramatically help
 185  *      unsuccessful lookups.  But unsuccessful lookups are almost always
 186  *      followed by insertions, and those slow down somewhat.  They
 187  *      also can help deletions somewhat.  Successful lookups aren't affected.
 188  *      So possibly a small win; probably nothing significant.
 189  */
 190
 191 #define IH_TABLE_HASH(obj, size)                                \
 192                 ((mach_port_index_t)(os_hash_kernel_pointer(obj) % (size)))
 193
 194 /*
 195  *      Routine:        ipc_hash_table_lookup
 196  *      Purpose:
 197  *              Converts (table, obj) -> (name, entry).
 198  *      Conditions:
 199  *              Must have read consistency on the table.
 200  */
 201
 202 boolean_t
 203 ipc_hash_table_lookup(
 204         ipc_entry_t             table,
 205         ipc_entry_num_t         size,
 206         ipc_object_t            obj,
 207         mach_port_name_t        *namep,
 208         ipc_entry_t             *entryp)
 209 {
 210         mach_port_index_t hindex, index, hdist;
 211
 212         if (obj == IO_NULL) {
 213                 return FALSE;
 214         }
 215
 216         hindex = IH_TABLE_HASH(obj, size);
 217         hdist  = 0;
 218
 219         /*
 220          *      Ideally, table[hindex].ie_index is the name we want.
 221          *      However, must check ie_object to verify this,
 222          *      because collisions can happen.  In case of a collision,
 223          *      search farther along in the clump.
 224          */
 225
 226         while ((index = table[hindex].ie_index) != 0) {
 227                 ipc_entry_t entry = &table[index];
 228
 229                 /*
 230                  * if our current displacement is strictly larger
 231                  * than the current slot one, then insertion would
 232                  * have stolen his place so we can't possibly exist.
 233                  */
 234                 if (hdist > table[hindex].ie_dist) {
 235                         return FALSE;
 236                 }
 237
 238                 /*
 239                  * If our current displacement is exactly the current
 240                  * slot displacement, then it can be a match, let's check.
 241                  */
 242                 if (hdist == table[hindex].ie_dist) {
 243                         assert(index < size);
 244                         if (entry->ie_object == obj) {
 245                                 *entryp = entry;
 246                                 *namep = MACH_PORT_MAKE(index,
 247                                     IE_BITS_GEN(entry->ie_bits));
 248                                 return TRUE;
 249                         }
 250                 } else {
 251                         assert(entry->ie_object != obj);
 252                 }
 253
 254                 if (hdist < IPC_ENTRY_DIST_MAX) {
 255                         /* peg the displacement distance at IPC_ENTRY_DIST_MAX */
 256                         ++hdist;
 257                 }
 258                 if (++hindex == size) {
 259                         hindex = 0;
 260                 }
 261         }
 262
 263         return FALSE;
 264 }
 265
 266 /*
 267  *      Routine:        ipc_hash_table_insert
 268  *      Purpose:
 269  *              Inserts an entry into the space's reverse hash table.
 270  *      Conditions:
 271  *              The space must be write-locked.
 272  */
 273
 274 void
 275 ipc_hash_table_insert(
 276         ipc_entry_t                     table,
 277         ipc_entry_num_t                 size,
 278         ipc_object_t                    obj,
 279         mach_port_index_t               index,
 280         __assert_only ipc_entry_t       entry)
 281 {
 282         mach_port_index_t hindex, hdist;
 283
 284         assert(index != 0);
 285         assert(obj != IO_NULL);
 286
 287         hindex = IH_TABLE_HASH(obj, size);
 288         hdist  = 0;
 289
 290         assert(entry == &table[index]);
 291         assert(entry->ie_object == obj);
 292
 293         /*
 294          *      We want to insert at hindex, but there may be collisions.
 295          *      If a collision occurs, search for the end of the clump
 296          *      and insert there.
 297          *
 298          *      However, Robin Hood steals from the rich, and as we go
 299          *      through the clump, if we go over an item that is less
 300          *      displaced than we'd be, we steal his slot and
 301          *      keep inserting him in our stead.
 302          */
 303         while (table[hindex].ie_index != 0) {
 304                 if (table[hindex].ie_dist < hdist) {
 305 #define swap(a, b)  ({ typeof(a) _tmp = (b); (b) = (a); (a) = _tmp; })
 306                         swap(hdist, table[hindex].ie_dist);
 307                         swap(index, table[hindex].ie_index);
 308 #undef swap
 309                 }
 310                 if (hdist < IPC_ENTRY_DIST_MAX) {
 311                         /* peg the displacement distance at IPC_ENTRY_DIST_MAX */
 312                         ++hdist;
 313                 }
 314                 if (++hindex == size) {
 315                         hindex = 0;
 316                 }
 317         }
 318
 319         table[hindex].ie_index = index;
 320         table[hindex].ie_dist = hdist;
 321 }
 322
 323 /*
 324  *      Routine:        ipc_hash_table_delete
 325  *      Purpose:
 326  *              Deletes an entry from the table's reverse hash.
 327  *      Conditions:
 328  *              Exclusive access to the table.
 329  */
 330
 331 void
 332 ipc_hash_table_delete(
 333         ipc_entry_t                     table,
 334         ipc_entry_num_t                 size,
 335         ipc_object_t                    obj,
 336         mach_port_index_t               index,
 337         __assert_only ipc_entry_t       entry)
 338 {
 339         mach_port_index_t hindex, dindex, dist;
 340
 341         assert(index != MACH_PORT_NULL);
 342         assert(obj != IO_NULL);
 343
 344         hindex = IH_TABLE_HASH(obj, size);
 345
 346         assert(entry == &table[index]);
 347         assert(entry->ie_object == obj);
 348
 349         /*
 350          *      First check we have the right hindex for this index.
 351          *      In case of collision, we have to search farther
 352          *      along in this clump.
 353          */
 354
 355         while (table[hindex].ie_index != index) {
 356                 if (++hindex == size) {
 357                         hindex = 0;
 358                 }
 359         }
 360
 361         /*
 362          *      Now we want to set table[hindex].ie_index = 0.
 363          *      But if we aren't the last index in a clump,
 364          *      this might cause problems for lookups of objects
 365          *      farther along in the clump that are displaced
 366          *      due to collisions.  Searches for them would fail
 367          *      at hindex instead of succeeding.
 368          *
 369          *      So we must check the clump after hindex for objects
 370          *      that are so displaced, and move one up to the new hole.
 371          *
 372          *              hindex - index of new hole in the clump
 373          *              dindex - index we are checking for a displaced object
 374          *
 375          *      When we move a displaced object up into the hole,
 376          *      it creates a new hole, and we have to repeat the process
 377          *      until we get to the end of the clump.
 378          */
 379
 380         for (;;) {
 381                 dindex = hindex + 1;
 382                 if (dindex == size) {
 383                         dindex = 0;
 384                 }
 385
 386                 /*
 387                  * If the next element is empty or isn't displaced,
 388                  * then lookup will end on the next element anyway,
 389                  * so we can leave the hole right here, we're done
 390                  */
 391                 index = table[dindex].ie_index;
 392                 dist  = table[dindex].ie_dist;
 393                 if (index == 0 || dist == 0) {
 394                         table[hindex].ie_index = 0;
 395                         table[hindex].ie_dist = 0;
 396                         return;
 397                 }
 398
 399                 /*
 400                  * Move this object closer to its own slot by occupying the hole.
 401                  * If its displacement was pegged, recompute it.
 402                  */
 403                 if (dist-- == IPC_ENTRY_DIST_MAX) {
 404                         uint32_t desired = IH_TABLE_HASH(table[index].ie_object, size);
 405                         if (hindex >= desired) {
 406                                 dist = hindex - desired;
 407                         } else {
 408                                 dist = hindex + size - desired;
 409                         }
 410                         if (dist > IPC_ENTRY_DIST_MAX) {
 411                                 dist = IPC_ENTRY_DIST_MAX;
 412                         }
 413                 }
 414
 415                 /*
 416                  * Move the displaced element closer to its ideal bucket,
 417                  * and keep shifting elements back.
 418                  */
 419                 table[hindex].ie_index = index;
 420                 table[hindex].ie_dist = dist;
 421                 hindex = dindex;
 422         }
 423 }