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 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 250void 251ipc_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 290void 291ipc_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 369