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