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 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 */ 90void 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 105boolean_t 106ipc_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 124void 125ipc_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 ipc_hash_table_insert(space->is_table, space->is_table_size, obj, index, entry); 135} 136 137/* 138 * Routine: ipc_hash_delete 139 * Purpose: 140 * Deletes an entry from the appropriate reverse hash table. 141 * Conditions: 142 * The space must be write-locked. 143 */ 144 145void 146ipc_hash_delete( 147 ipc_space_t space, 148 ipc_object_t obj, 149 mach_port_name_t name, 150 ipc_entry_t entry) 151{ 152 mach_port_index_t index; 153 154 index = MACH_PORT_INDEX(name); 155 ipc_hash_table_delete(space->is_table, space->is_table_size, obj, index, entry); 156} 157 158/* 159 * Each space has a local reverse hash table, which holds 160 * entries from the space's table. In fact, the hash table 161 * just uses a field (ie_index) in the table itself. 162 * 163 * The local hash table is an open-addressing hash table, 164 * which means that when a collision occurs, instead of 165 * throwing the entry into a bucket, the entry is rehashed 166 * to another position in the table. In this case the rehash 167 * is very simple: linear probing (ie, just increment the position). 168 * This simple rehash makes deletions tractable (they're still a pain), 169 * but it means that collisions tend to build up into clumps. 170 * 171 * Because at least one entry in the table (index 0) is always unused, 172 * there will always be room in the reverse hash table. If a table 173 * with n slots gets completely full, the reverse hash table will 174 * have one giant clump of n-1 slots and one free slot somewhere. 175 * Because entries are only entered into the reverse table if they 176 * are pure send rights (not receive, send-once, port-set, 177 * or dead-name rights), and free entries of course aren't entered, 178 * I expect the reverse hash table won't get unreasonably full. 179 * 180 * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2, 181 * pp. 135-142.) may be desirable here. They can dramatically help 182 * unsuccessful lookups. But unsuccessful lookups are almost always 183 * followed by insertions, and those slow down somewhat. They 184 * also can help deletions somewhat. Successful lookups aren't affected. 185 * So possibly a small win; probably nothing significant. 186 */ 187 188#define IH_TABLE_HASH(obj, size) \ 189 ((mach_port_index_t)((((uintptr_t) (obj)) >> 6) % (size))) 190 191/* 192 * Routine: ipc_hash_table_lookup 193 * Purpose: 194 * Converts (table, obj) -> (name, entry). 195 * Conditions: 196 * Must have read consistency on the table. 197 */ 198 199boolean_t 200ipc_hash_table_lookup( 201 ipc_entry_t table, 202 ipc_entry_num_t size, 203 ipc_object_t obj, 204 mach_port_name_t *namep, 205 ipc_entry_t *entryp) 206{ 207 mach_port_index_t hindex, index; 208 209 if (obj == IO_NULL) { 210 return FALSE; 211 } 212 213 hindex = IH_TABLE_HASH(obj, size); 214 215 /* 216 * Ideally, table[hindex].ie_index is the name we want. 217 * However, must check ie_object to verify this, 218 * because collisions can happen. In case of a collision, 219 * search farther along in the clump. 220 */ 221 222 while ((index = table[hindex].ie_index) != 0) { 223 ipc_entry_t entry; 224 225 assert(index < size); 226 entry = &table[index]; 227 if (entry->ie_object == obj) { 228 *entryp = entry; 229 *namep = MACH_PORT_MAKE(index, 230 IE_BITS_GEN(entry->ie_bits)); 231 return TRUE; 232 } 233 234 if (++hindex == size) 235 hindex = 0; 236 } 237 238 return FALSE; 239} 240 241/* 242 * Routine: ipc_hash_table_insert 243 * Purpose: 244 * Inserts an entry into the space's reverse hash table. 245 * Conditions: 246 * The space must be write-locked. 247 */ 248 249void 250ipc_hash_table_insert( 251 ipc_entry_t table, 252 ipc_entry_num_t size, 253 ipc_object_t obj, 254 mach_port_index_t index, 255 __assert_only ipc_entry_t entry) 256{ 257 mach_port_index_t hindex; 258 259 assert(index != 0); 260 assert(obj != IO_NULL); 261 262 hindex = IH_TABLE_HASH(obj, size); 263 264 assert(entry == &table[index]); 265 assert(entry->ie_object == obj); 266 267 /* 268 * We want to insert at hindex, but there may be collisions. 269 * If a collision occurs, search for the end of the clump 270 * and insert there. 271 */ 272 273 while (table[hindex].ie_index != 0) { 274 if (++hindex == size) 275 hindex = 0; 276 } 277 278 table[hindex].ie_index = index; 279} 280 281/* 282 * Routine: ipc_hash_table_delete 283 * Purpose: 284 * Deletes an entry from the table's reverse hash. 285 * Conditions: 286 * Exclusive access to the table. 287 */ 288 289void 290ipc_hash_table_delete( 291 ipc_entry_t table, 292 ipc_entry_num_t size, 293 ipc_object_t obj, 294 mach_port_index_t index, 295 __assert_only ipc_entry_t entry) 296{ 297 mach_port_index_t hindex, dindex; 298 299 assert(index != MACH_PORT_NULL); 300 assert(obj != IO_NULL); 301 302 hindex = IH_TABLE_HASH(obj, size); 303 304 assert(entry == &table[index]); 305 assert(entry->ie_object == obj); 306 307 /* 308 * First check we have the right hindex for this index. 309 * In case of collision, we have to search farther 310 * along in this clump. 311 */ 312 313 while (table[hindex].ie_index != index) { 314 if (++hindex == size) 315 hindex = 0; 316 } 317 318 /* 319 * Now we want to set table[hindex].ie_index = 0. 320 * But if we aren't the last index in a clump, 321 * this might cause problems for lookups of objects 322 * farther along in the clump that are displaced 323 * due to collisions. Searches for them would fail 324 * at hindex instead of succeeding. 325 * 326 * So we must check the clump after hindex for objects 327 * that are so displaced, and move one up to the new hole. 328 * 329 * hindex - index of new hole in the clump 330 * dindex - index we are checking for a displaced object 331 * 332 * When we move a displaced object up into the hole, 333 * it creates a new hole, and we have to repeat the process 334 * until we get to the end of the clump. 335 */ 336 337 for (dindex = hindex; index != 0; hindex = dindex) { 338 for (;;) { 339 mach_port_index_t tindex; 340 ipc_object_t tobj; 341 342 if (++dindex == size) 343 dindex = 0; 344 assert(dindex != hindex); 345 346 /* are we at the end of the clump? */ 347 348 index = table[dindex].ie_index; 349 if (index == 0) 350 break; 351 352 /* is this a displaced object? */ 353 354 tobj = table[index].ie_object; 355 assert(tobj != IO_NULL); 356 tindex = IH_TABLE_HASH(tobj, size); 357 358 if ((dindex < hindex) ? 359 ((dindex < tindex) && (tindex <= hindex)) : 360 ((dindex < tindex) || (tindex <= hindex))) 361 break; 362 } 363 364 table[hindex].ie_index = index; 365 } 366} 367 368