![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ipc_hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / OSKit-Mach / ipc|
Return to ipc_hash.c CVS log | Up to [GnuMach] / OSKit-Mach / ipc |
1.1 ! root 1: /* ! 2: * Mach Operating System ! 3: * Copyright (c) 1991,1990,1989 Carnegie Mellon University ! 4: * All Rights Reserved. ! 5: * ! 6: * Permission to use, copy, modify and distribute this software and its ! 7: * documentation is hereby granted, provided that both the copyright ! 8: * notice and this permission notice appear in all copies of the ! 9: * software, derivative works or modified versions, and any portions ! 10: * thereof, and that both notices appear in supporting documentation. ! 11: * ! 12: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" ! 13: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR ! 14: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. ! 15: * ! 16: * Carnegie Mellon requests users of this software to return to ! 17: * ! 18: * Software Distribution Coordinator or [email protected] ! 19: * School of Computer Science ! 20: * Carnegie Mellon University ! 21: * Pittsburgh PA 15213-3890 ! 22: * ! 23: * any improvements or extensions that they make and grant Carnegie Mellon ! 24: * the rights to redistribute these changes. ! 25: */ ! 26: /* ! 27: * File: ipc/ipc_hash.c ! 28: * Author: Rich Draves ! 29: * Date: 1989 ! 30: * ! 31: * Entry hash table operations. ! 32: */ ! 33: ! 34: #include <mach/boolean.h> ! 35: #include <mach/port.h> ! 36: #include <kern/lock.h> ! 37: #include <kern/kalloc.h> ! 38: #include <ipc/port.h> ! 39: #include <ipc/ipc_space.h> ! 40: #include <ipc/ipc_object.h> ! 41: #include <ipc/ipc_entry.h> ! 42: #include <ipc/ipc_hash.h> ! 43: #include <ipc/ipc_init.h> ! 44: #include <ipc/ipc_types.h> ! 45: ! 46: #include <mach_ipc_debug.h> ! 47: #if MACH_IPC_DEBUG ! 48: #include <mach/kern_return.h> ! 49: #include <mach_debug/hash_info.h> ! 50: #include <vm/vm_map.h> ! 51: #include <vm/vm_kern.h> ! 52: #include <vm/vm_user.h> ! 53: #endif ! 54: ! 55: ! 56: ! 57: /* ! 58: * Routine: ipc_hash_lookup ! 59: * Purpose: ! 60: * Converts (space, obj) -> (name, entry). ! 61: * Returns TRUE if an entry was found. ! 62: * Conditions: ! 63: * The space must be locked (read or write) throughout. ! 64: */ ! 65: ! 66: boolean_t ! 67: ipc_hash_lookup(space, obj, namep, entryp) ! 68: ipc_space_t space; ! 69: ipc_object_t obj; ! 70: mach_port_t *namep; ! 71: ipc_entry_t *entryp; ! 72: { ! 73: return (ipc_hash_local_lookup(space, obj, namep, entryp) || ! 74: ((space->is_tree_hash > 0) && ! 75: ipc_hash_global_lookup(space, obj, namep, ! 76: (ipc_tree_entry_t *) entryp))); ! 77: } ! 78: ! 79: /* ! 80: * Routine: ipc_hash_insert ! 81: * Purpose: ! 82: * Inserts an entry into the appropriate reverse hash table, ! 83: * so that ipc_hash_lookup will find it. ! 84: * Conditions: ! 85: * The space must be write-locked. ! 86: */ ! 87: ! 88: void ! 89: ipc_hash_insert( ! 90: ipc_space_t space, ! 91: ipc_object_t obj, ! 92: mach_port_t name, ! 93: ipc_entry_t entry) ! 94: { ! 95: mach_port_index_t index; ! 96: ! 97: index = MACH_PORT_INDEX(name); ! 98: if ((index < space->is_table_size) && ! 99: (entry == &space->is_table[index])) ! 100: ipc_hash_local_insert(space, obj, index, entry); ! 101: else ! 102: ipc_hash_global_insert(space, obj, name, ! 103: (ipc_tree_entry_t) entry); ! 104: } ! 105: ! 106: /* ! 107: * Routine: ipc_hash_delete ! 108: * Purpose: ! 109: * Deletes an entry from the appropriate reverse hash table. ! 110: * Conditions: ! 111: * The space must be write-locked. ! 112: */ ! 113: ! 114: void ! 115: ipc_hash_delete( ! 116: ipc_space_t space, ! 117: ipc_object_t obj, ! 118: mach_port_t name, ! 119: ipc_entry_t entry) ! 120: { ! 121: mach_port_index_t index; ! 122: ! 123: index = MACH_PORT_INDEX(name); ! 124: if ((index < space->is_table_size) && ! 125: (entry == &space->is_table[index])) ! 126: ipc_hash_local_delete(space, obj, index, entry); ! 127: else ! 128: ipc_hash_global_delete(space, obj, name, ! 129: (ipc_tree_entry_t) entry); ! 130: } ! 131: ! 132: /* ! 133: * The global reverse hash table holds splay tree entries. ! 134: * It is a simple open-chaining hash table with singly-linked buckets. ! 135: * Each bucket is locked separately, with an exclusive lock. ! 136: * Within each bucket, move-to-front is used. ! 137: */ ! 138: ! 139: ipc_hash_index_t ipc_hash_global_size; ! 140: ipc_hash_index_t ipc_hash_global_mask; ! 141: ! 142: #define IH_GLOBAL_HASH(space, obj) \ ! 143: (((((ipc_hash_index_t) ((vm_offset_t)space)) >> 4) + \ ! 144: (((ipc_hash_index_t) ((vm_offset_t)obj)) >> 6)) & \ ! 145: ipc_hash_global_mask) ! 146: ! 147: typedef struct ipc_hash_global_bucket { ! 148: decl_simple_lock_data(, ihgb_lock_data) ! 149: ipc_tree_entry_t ihgb_head; ! 150: } *ipc_hash_global_bucket_t; ! 151: ! 152: #define IHGB_NULL ((ipc_hash_global_bucket_t) 0) ! 153: ! 154: #define ihgb_lock_init(ihgb) simple_lock_init(&(ihgb)->ihgb_lock_data) ! 155: #define ihgb_lock(ihgb) simple_lock(&(ihgb)->ihgb_lock_data) ! 156: #define ihgb_unlock(ihgb) simple_unlock(&(ihgb)->ihgb_lock_data) ! 157: ! 158: ipc_hash_global_bucket_t ipc_hash_global_table; ! 159: ! 160: /* ! 161: * Routine: ipc_hash_global_lookup ! 162: * Purpose: ! 163: * Converts (space, obj) -> (name, entry). ! 164: * Looks in the global table, for splay tree entries. ! 165: * Returns TRUE if an entry was found. ! 166: * Conditions: ! 167: * The space must be locked (read or write) throughout. ! 168: */ ! 169: ! 170: boolean_t ! 171: ipc_hash_global_lookup( ! 172: ipc_space_t space, ! 173: ipc_object_t obj, ! 174: mach_port_t *namep, ! 175: ipc_tree_entry_t *entryp) ! 176: { ! 177: ipc_hash_global_bucket_t bucket; ! 178: ipc_tree_entry_t this, *last; ! 179: ! 180: assert(space != IS_NULL); ! 181: assert(obj != IO_NULL); ! 182: ! 183: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ! 184: ihgb_lock(bucket); ! 185: ! 186: if ((this = bucket->ihgb_head) != ITE_NULL) { ! 187: if ((this->ite_object == obj) && ! 188: (this->ite_space == space)) { ! 189: /* found it at front; no need to move */ ! 190: ! 191: *namep = this->ite_name; ! 192: *entryp = this; ! 193: } else for (last = &this->ite_next; ! 194: (this = *last) != ITE_NULL; ! 195: last = &this->ite_next) { ! 196: if ((this->ite_object == obj) && ! 197: (this->ite_space == space)) { ! 198: /* found it; move to front */ ! 199: ! 200: *last = this->ite_next; ! 201: this->ite_next = bucket->ihgb_head; ! 202: bucket->ihgb_head = this; ! 203: ! 204: *namep = this->ite_name; ! 205: *entryp = this; ! 206: break; ! 207: } ! 208: } ! 209: } ! 210: ! 211: ihgb_unlock(bucket); ! 212: return this != ITE_NULL; ! 213: } ! 214: ! 215: /* ! 216: * Routine: ipc_hash_global_insert ! 217: * Purpose: ! 218: * Inserts an entry into the global reverse hash table. ! 219: * Conditions: ! 220: * The space must be write-locked. ! 221: */ ! 222: ! 223: void ! 224: ipc_hash_global_insert( ! 225: ipc_space_t space, ! 226: ipc_object_t obj, ! 227: mach_port_t name, ! 228: ipc_tree_entry_t entry) ! 229: { ! 230: ipc_hash_global_bucket_t bucket; ! 231: ! 232: ! 233: assert(entry->ite_name == name); ! 234: assert(space != IS_NULL); ! 235: assert(entry->ite_space == space); ! 236: assert(obj != IO_NULL); ! 237: assert(entry->ite_object == obj); ! 238: ! 239: space->is_tree_hash++; ! 240: assert(space->is_tree_hash <= space->is_tree_total); ! 241: ! 242: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ! 243: ihgb_lock(bucket); ! 244: ! 245: /* insert at front of bucket */ ! 246: ! 247: entry->ite_next = bucket->ihgb_head; ! 248: bucket->ihgb_head = entry; ! 249: ! 250: ihgb_unlock(bucket); ! 251: } ! 252: ! 253: /* ! 254: * Routine: ipc_hash_global_delete ! 255: * Purpose: ! 256: * Deletes an entry from the global reverse hash table. ! 257: * Conditions: ! 258: * The space must be write-locked. ! 259: */ ! 260: ! 261: void ! 262: ipc_hash_global_delete( ! 263: ipc_space_t space, ! 264: ipc_object_t obj, ! 265: mach_port_t name, ! 266: ipc_tree_entry_t entry) ! 267: { ! 268: ipc_hash_global_bucket_t bucket; ! 269: ipc_tree_entry_t this, *last; ! 270: ! 271: assert(entry->ite_name == name); ! 272: assert(space != IS_NULL); ! 273: assert(entry->ite_space == space); ! 274: assert(obj != IO_NULL); ! 275: assert(entry->ite_object == obj); ! 276: ! 277: assert(space->is_tree_hash > 0); ! 278: space->is_tree_hash--; ! 279: ! 280: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ! 281: ihgb_lock(bucket); ! 282: ! 283: for (last = &bucket->ihgb_head; ! 284: (this = *last) != ITE_NULL; ! 285: last = &this->ite_next) { ! 286: if (this == entry) { ! 287: /* found it; remove from bucket */ ! 288: ! 289: *last = this->ite_next; ! 290: break; ! 291: } ! 292: } ! 293: assert(this != ITE_NULL); ! 294: ! 295: ihgb_unlock(bucket); ! 296: } ! 297: ! 298: /* ! 299: * Each space has a local reverse hash table, which holds ! 300: * entries from the space's table. In fact, the hash table ! 301: * just uses a field (ie_index) in the table itself. ! 302: * ! 303: * The local hash table is an open-addressing hash table, ! 304: * which means that when a collision occurs, instead of ! 305: * throwing the entry into a bucket, the entry is rehashed ! 306: * to another position in the table. In this case the rehash ! 307: * is very simple: linear probing (ie, just increment the position). ! 308: * This simple rehash makes deletions tractable (they're still a pain), ! 309: * but it means that collisions tend to build up into clumps. ! 310: * ! 311: * Because at least one entry in the table (index 0) is always unused, ! 312: * there will always be room in the reverse hash table. If a table ! 313: * with n slots gets completely full, the reverse hash table will ! 314: * have one giant clump of n-1 slots and one free slot somewhere. ! 315: * Because entries are only entered into the reverse table if they ! 316: * are pure send rights (not receive, send-once, port-set, ! 317: * or dead-name rights), and free entries of course aren't entered, ! 318: * I expect the reverse hash table won't get unreasonably full. ! 319: * ! 320: * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2, ! 321: * pp. 135-142.) may be desirable here. They can dramatically help ! 322: * unsuccessful lookups. But unsuccessful lookups are almost always ! 323: * followed by insertions, and those slow down somewhat. They ! 324: * also can help deletions somewhat. Successful lookups aren't affected. ! 325: * So possibly a small win; probably nothing significant. ! 326: */ ! 327: ! 328: #define IH_LOCAL_HASH(obj, size) \ ! 329: ((((mach_port_index_t) (obj)) >> 6) % (size)) ! 330: ! 331: /* ! 332: * Routine: ipc_hash_local_lookup ! 333: * Purpose: ! 334: * Converts (space, obj) -> (name, entry). ! 335: * Looks in the space's local table, for table entries. ! 336: * Returns TRUE if an entry was found. ! 337: * Conditions: ! 338: * The space must be locked (read or write) throughout. ! 339: */ ! 340: ! 341: boolean_t ! 342: ipc_hash_local_lookup( ! 343: ipc_space_t space, ! 344: ipc_object_t obj, ! 345: mach_port_t *namep, ! 346: ipc_entry_t *entryp) ! 347: { ! 348: ipc_entry_t table; ! 349: ipc_entry_num_t size; ! 350: mach_port_index_t hindex, index; ! 351: ! 352: assert(space != IS_NULL); ! 353: assert(obj != IO_NULL); ! 354: ! 355: table = space->is_table; ! 356: size = space->is_table_size; ! 357: hindex = IH_LOCAL_HASH(obj, size); ! 358: ! 359: /* ! 360: * Ideally, table[hindex].ie_index is the name we want. ! 361: * However, must check ie_object to verify this, ! 362: * because collisions can happen. In case of a collision, ! 363: * search farther along in the clump. ! 364: */ ! 365: ! 366: while ((index = table[hindex].ie_index) != 0) { ! 367: ipc_entry_t entry = &table[index]; ! 368: ! 369: if (entry->ie_object == obj) { ! 370: *namep = MACH_PORT_MAKEB(index, entry->ie_bits); ! 371: *entryp = entry; ! 372: return TRUE; ! 373: } ! 374: ! 375: if (++hindex == size) ! 376: hindex = 0; ! 377: } ! 378: ! 379: return FALSE; ! 380: } ! 381: ! 382: /* ! 383: * Routine: ipc_hash_local_insert ! 384: * Purpose: ! 385: * Inserts an entry into the space's reverse hash table. ! 386: * Conditions: ! 387: * The space must be write-locked. ! 388: */ ! 389: ! 390: void ! 391: ipc_hash_local_insert( ! 392: ipc_space_t space, ! 393: ipc_object_t obj, ! 394: mach_port_index_t index, ! 395: ipc_entry_t entry) ! 396: { ! 397: ipc_entry_t table; ! 398: ipc_entry_num_t size; ! 399: mach_port_index_t hindex; ! 400: ! 401: assert(index != 0); ! 402: assert(space != IS_NULL); ! 403: assert(obj != IO_NULL); ! 404: ! 405: table = space->is_table; ! 406: size = space->is_table_size; ! 407: hindex = IH_LOCAL_HASH(obj, size); ! 408: ! 409: assert(entry == &table[index]); ! 410: assert(entry->ie_object == obj); ! 411: ! 412: /* ! 413: * We want to insert at hindex, but there may be collisions. ! 414: * If a collision occurs, search for the end of the clump ! 415: * and insert there. ! 416: */ ! 417: ! 418: while (table[hindex].ie_index != 0) { ! 419: if (++hindex == size) ! 420: hindex = 0; ! 421: } ! 422: ! 423: table[hindex].ie_index = index; ! 424: } ! 425: ! 426: /* ! 427: * Routine: ipc_hash_local_delete ! 428: * Purpose: ! 429: * Deletes an entry from the space's reverse hash table. ! 430: * Conditions: ! 431: * The space must be write-locked. ! 432: */ ! 433: ! 434: void ! 435: ipc_hash_local_delete( ! 436: ipc_space_t space, ! 437: ipc_object_t obj, ! 438: mach_port_index_t index, ! 439: ipc_entry_t entry) ! 440: { ! 441: ipc_entry_t table; ! 442: ipc_entry_num_t size; ! 443: mach_port_index_t hindex, dindex; ! 444: ! 445: assert(index != MACH_PORT_NULL); ! 446: assert(space != IS_NULL); ! 447: assert(obj != IO_NULL); ! 448: ! 449: table = space->is_table; ! 450: size = space->is_table_size; ! 451: hindex = IH_LOCAL_HASH(obj, size); ! 452: ! 453: assert(entry == &table[index]); ! 454: assert(entry->ie_object == obj); ! 455: ! 456: /* ! 457: * First check we have the right hindex for this index. ! 458: * In case of collision, we have to search farther ! 459: * along in this clump. ! 460: */ ! 461: ! 462: while (table[hindex].ie_index != index) { ! 463: if (table[hindex].ie_index == 0) ! 464: { ! 465: static int gak = 0; ! 466: if (gak == 0) ! 467: { ! 468: printf("gak! entry wasn't in hash table!\n"); ! 469: gak = 1; ! 470: } ! 471: return; ! 472: } ! 473: if (++hindex == size) ! 474: hindex = 0; ! 475: } ! 476: ! 477: /* ! 478: * Now we want to set table[hindex].ie_index = 0. ! 479: * But if we aren't the last index in a clump, ! 480: * this might cause problems for lookups of objects ! 481: * farther along in the clump that are displaced ! 482: * due to collisions. Searches for them would fail ! 483: * at hindex instead of succeeding. ! 484: * ! 485: * So we must check the clump after hindex for objects ! 486: * that are so displaced, and move one up to the new hole. ! 487: * ! 488: * hindex - index of new hole in the clump ! 489: * dindex - index we are checking for a displaced object ! 490: * ! 491: * When we move a displaced object up into the hole, ! 492: * it creates a new hole, and we have to repeat the process ! 493: * until we get to the end of the clump. ! 494: */ ! 495: ! 496: for (dindex = hindex; index != 0; hindex = dindex) { ! 497: for (;;) { ! 498: mach_port_index_t tindex; ! 499: ipc_object_t tobj; ! 500: ! 501: if (++dindex == size) ! 502: dindex = 0; ! 503: assert(dindex != hindex); ! 504: ! 505: /* are we at the end of the clump? */ ! 506: ! 507: index = table[dindex].ie_index; ! 508: if (index == 0) ! 509: break; ! 510: ! 511: /* is this a displaced object? */ ! 512: ! 513: tobj = table[index].ie_object; ! 514: assert(tobj != IO_NULL); ! 515: tindex = IH_LOCAL_HASH(tobj, size); ! 516: ! 517: if ((dindex < hindex) ? ! 518: ((dindex < tindex) && (tindex <= hindex)) : ! 519: ((dindex < tindex) || (tindex <= hindex))) ! 520: break; ! 521: } ! 522: ! 523: table[hindex].ie_index = index; ! 524: } ! 525: } ! 526: ! 527: /* ! 528: * Routine: ipc_hash_init ! 529: * Purpose: ! 530: * Initialize the reverse hash table implementation. ! 531: */ ! 532: ! 533: void ! 534: ipc_hash_init(void) ! 535: { ! 536: ipc_hash_index_t i; ! 537: ! 538: /* if not configured, initialize ipc_hash_global_size */ ! 539: ! 540: if (ipc_hash_global_size == 0) { ! 541: ipc_hash_global_size = ipc_tree_entry_max >> 8; ! 542: if (ipc_hash_global_size < 32) ! 543: ipc_hash_global_size = 32; ! 544: } ! 545: ! 546: /* make sure it is a power of two */ ! 547: ! 548: ipc_hash_global_mask = ipc_hash_global_size - 1; ! 549: if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) { ! 550: natural_t bit; ! 551: ! 552: /* round up to closest power of two */ ! 553: ! 554: for (bit = 1;; bit <<= 1) { ! 555: ipc_hash_global_mask |= bit; ! 556: ipc_hash_global_size = ipc_hash_global_mask + 1; ! 557: ! 558: if ((ipc_hash_global_size & ipc_hash_global_mask) == 0) ! 559: break; ! 560: } ! 561: } ! 562: ! 563: /* allocate ipc_hash_global_table */ ! 564: ! 565: ipc_hash_global_table = (ipc_hash_global_bucket_t) ! 566: kalloc((vm_size_t) (ipc_hash_global_size * ! 567: sizeof(struct ipc_hash_global_bucket))); ! 568: assert(ipc_hash_global_table != IHGB_NULL); ! 569: ! 570: /* and initialize it */ ! 571: ! 572: for (i = 0; i < ipc_hash_global_size; i++) { ! 573: ipc_hash_global_bucket_t bucket; ! 574: ! 575: bucket = &ipc_hash_global_table[i]; ! 576: ihgb_lock_init(bucket); ! 577: bucket->ihgb_head = ITE_NULL; ! 578: } ! 579: } ! 580: ! 581: #if MACH_IPC_DEBUG ! 582: ! 583: /* ! 584: * Routine: ipc_hash_info ! 585: * Purpose: ! 586: * Return information about the global reverse hash table. ! 587: * Fills the buffer with as much information as possible ! 588: * and returns the desired size of the buffer. ! 589: * Conditions: ! 590: * Nothing locked. The caller should provide ! 591: * possibly-pageable memory. ! 592: */ ! 593: ! 594: ! 595: ipc_hash_index_t ! 596: ipc_hash_info( ! 597: hash_info_bucket_t *info, ! 598: mach_msg_type_number_t count) ! 599: { ! 600: ipc_hash_index_t i; ! 601: ! 602: if (ipc_hash_global_size < count) ! 603: count = ipc_hash_global_size; ! 604: ! 605: for (i = 0; i < count; i++) { ! 606: ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i]; ! 607: unsigned int bucket_count = 0; ! 608: ipc_tree_entry_t entry; ! 609: ! 610: ihgb_lock(bucket); ! 611: for (entry = bucket->ihgb_head; ! 612: entry != ITE_NULL; ! 613: entry = entry->ite_next) ! 614: bucket_count++; ! 615: ihgb_unlock(bucket); ! 616: ! 617: /* don't touch pageable memory while holding locks */ ! 618: info[i].hib_count = bucket_count; ! 619: } ! 620: ! 621: return ipc_hash_global_size; ! 622: } ! 623: ! 624: #endif /* MACH_IPC_DEBUG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.