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 */ 91void 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 106boolean_t 107ipc_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 125void 126ipc_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 146void 147ipc_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 200boolean_t 201ipc_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 248void 249ipc_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 288void 289ipc_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 367