![[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] / Gnu-Mach / ipc|
Return to ipc_hash.c CVS log | Up to [GnuMach] / Gnu-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: typedef natural_t ipc_hash_index_t; ! 140: ! 141: ipc_hash_index_t ipc_hash_global_size; ! 142: ipc_hash_index_t ipc_hash_global_mask; ! 143: ! 144: #define IH_GLOBAL_HASH(space, obj) \ ! 145: (((((ipc_hash_index_t) ((vm_offset_t)space)) >> 4) + \ ! 146: (((ipc_hash_index_t) ((vm_offset_t)obj)) >> 6)) & \ ! 147: ipc_hash_global_mask) ! 148: ! 149: typedef struct ipc_hash_global_bucket { ! 150: decl_simple_lock_data(, ihgb_lock_data) ! 151: ipc_tree_entry_t ihgb_head; ! 152: } *ipc_hash_global_bucket_t; ! 153: ! 154: #define IHGB_NULL ((ipc_hash_global_bucket_t) 0) ! 155: ! 156: #define ihgb_lock_init(ihgb) simple_lock_init(&(ihgb)->ihgb_lock_data) ! 157: #define ihgb_lock(ihgb) simple_lock(&(ihgb)->ihgb_lock_data) ! 158: #define ihgb_unlock(ihgb) simple_unlock(&(ihgb)->ihgb_lock_data) ! 159: ! 160: ipc_hash_global_bucket_t ipc_hash_global_table; ! 161: ! 162: /* ! 163: * Routine: ipc_hash_global_lookup ! 164: * Purpose: ! 165: * Converts (space, obj) -> (name, entry). ! 166: * Looks in the global table, for splay tree entries. ! 167: * Returns TRUE if an entry was found. ! 168: * Conditions: ! 169: * The space must be locked (read or write) throughout. ! 170: */ ! 171: ! 172: boolean_t ! 173: ipc_hash_global_lookup( ! 174: ipc_space_t space, ! 175: ipc_object_t obj, ! 176: mach_port_t *namep, ! 177: ipc_tree_entry_t *entryp) ! 178: { ! 179: ipc_hash_global_bucket_t bucket; ! 180: ipc_tree_entry_t this, *last; ! 181: ! 182: assert(space != IS_NULL); ! 183: assert(obj != IO_NULL); ! 184: ! 185: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ! 186: ihgb_lock(bucket); ! 187: ! 188: if ((this = bucket->ihgb_head) != ITE_NULL) { ! 189: if ((this->ite_object == obj) && ! 190: (this->ite_space == space)) { ! 191: /* found it at front; no need to move */ ! 192: ! 193: *namep = this->ite_name; ! 194: *entryp = this; ! 195: } else for (last = &this->ite_next; ! 196: (this = *last) != ITE_NULL; ! 197: last = &this->ite_next) { ! 198: if ((this->ite_object == obj) && ! 199: (this->ite_space == space)) { ! 200: /* found it; move to front */ ! 201: ! 202: *last = this->ite_next; ! 203: this->ite_next = bucket->ihgb_head; ! 204: bucket->ihgb_head = this; ! 205: ! 206: *namep = this->ite_name; ! 207: *entryp = this; ! 208: break; ! 209: } ! 210: } ! 211: } ! 212: ! 213: ihgb_unlock(bucket); ! 214: return this != ITE_NULL; ! 215: } ! 216: ! 217: /* ! 218: * Routine: ipc_hash_global_insert ! 219: * Purpose: ! 220: * Inserts an entry into the global reverse hash table. ! 221: * Conditions: ! 222: * The space must be write-locked. ! 223: */ ! 224: ! 225: void ! 226: ipc_hash_global_insert( ! 227: ipc_space_t space, ! 228: ipc_object_t obj, ! 229: mach_port_t name, ! 230: ipc_tree_entry_t entry) ! 231: { ! 232: ipc_hash_global_bucket_t bucket; ! 233: ! 234: ! 235: assert(entry->ite_name == name); ! 236: assert(space != IS_NULL); ! 237: assert(entry->ite_space == space); ! 238: assert(obj != IO_NULL); ! 239: assert(entry->ite_object == obj); ! 240: ! 241: space->is_tree_hash++; ! 242: assert(space->is_tree_hash <= space->is_tree_total); ! 243: ! 244: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ! 245: ihgb_lock(bucket); ! 246: ! 247: /* insert at front of bucket */ ! 248: ! 249: entry->ite_next = bucket->ihgb_head; ! 250: bucket->ihgb_head = entry; ! 251: ! 252: ihgb_unlock(bucket); ! 253: } ! 254: ! 255: /* ! 256: * Routine: ipc_hash_global_delete ! 257: * Purpose: ! 258: * Deletes an entry from the global reverse hash table. ! 259: * Conditions: ! 260: * The space must be write-locked. ! 261: */ ! 262: ! 263: void ! 264: ipc_hash_global_delete( ! 265: ipc_space_t space, ! 266: ipc_object_t obj, ! 267: mach_port_t name, ! 268: ipc_tree_entry_t entry) ! 269: { ! 270: ipc_hash_global_bucket_t bucket; ! 271: ipc_tree_entry_t this, *last; ! 272: ! 273: assert(entry->ite_name == name); ! 274: assert(space != IS_NULL); ! 275: assert(entry->ite_space == space); ! 276: assert(obj != IO_NULL); ! 277: assert(entry->ite_object == obj); ! 278: ! 279: assert(space->is_tree_hash > 0); ! 280: space->is_tree_hash--; ! 281: ! 282: bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)]; ! 283: ihgb_lock(bucket); ! 284: ! 285: for (last = &bucket->ihgb_head; ! 286: (this = *last) != ITE_NULL; ! 287: last = &this->ite_next) { ! 288: if (this == entry) { ! 289: /* found it; remove from bucket */ ! 290: ! 291: *last = this->ite_next; ! 292: break; ! 293: } ! 294: } ! 295: assert(this != ITE_NULL); ! 296: ! 297: ihgb_unlock(bucket); ! 298: } ! 299: ! 300: /* ! 301: * Each space has a local reverse hash table, which holds ! 302: * entries from the space's table. In fact, the hash table ! 303: * just uses a field (ie_index) in the table itself. ! 304: * ! 305: * The local hash table is an open-addressing hash table, ! 306: * which means that when a collision occurs, instead of ! 307: * throwing the entry into a bucket, the entry is rehashed ! 308: * to another position in the table. In this case the rehash ! 309: * is very simple: linear probing (ie, just increment the position). ! 310: * This simple rehash makes deletions tractable (they're still a pain), ! 311: * but it means that collisions tend to build up into clumps. ! 312: * ! 313: * Because at least one entry in the table (index 0) is always unused, ! 314: * there will always be room in the reverse hash table. If a table ! 315: * with n slots gets completely full, the reverse hash table will ! 316: * have one giant clump of n-1 slots and one free slot somewhere. ! 317: * Because entries are only entered into the reverse table if they ! 318: * are pure send rights (not receive, send-once, port-set, ! 319: * or dead-name rights), and free entries of course aren't entered, ! 320: * I expect the reverse hash table won't get unreasonably full. ! 321: * ! 322: * Ordered hash tables (Amble & Knuth, Computer Journal, v. 17, no. 2, ! 323: * pp. 135-142.) may be desirable here. They can dramatically help ! 324: * unsuccessful lookups. But unsuccessful lookups are almost always ! 325: * followed by insertions, and those slow down somewhat. They ! 326: * also can help deletions somewhat. Successful lookups aren't affected. ! 327: * So possibly a small win; probably nothing significant. ! 328: */ ! 329: ! 330: #define IH_LOCAL_HASH(obj, size) \ ! 331: ((((mach_port_index_t) (obj)) >> 6) % (size)) ! 332: ! 333: /* ! 334: * Routine: ipc_hash_local_lookup ! 335: * Purpose: ! 336: * Converts (space, obj) -> (name, entry). ! 337: * Looks in the space's local table, for table entries. ! 338: * Returns TRUE if an entry was found. ! 339: * Conditions: ! 340: * The space must be locked (read or write) throughout. ! 341: */ ! 342: ! 343: boolean_t ! 344: ipc_hash_local_lookup( ! 345: ipc_space_t space, ! 346: ipc_object_t obj, ! 347: mach_port_t *namep, ! 348: ipc_entry_t *entryp) ! 349: { ! 350: ipc_entry_t table; ! 351: ipc_entry_num_t size; ! 352: mach_port_index_t hindex, index; ! 353: ! 354: assert(space != IS_NULL); ! 355: assert(obj != IO_NULL); ! 356: ! 357: table = space->is_table; ! 358: size = space->is_table_size; ! 359: hindex = IH_LOCAL_HASH(obj, size); ! 360: ! 361: /* ! 362: * Ideally, table[hindex].ie_index is the name we want. ! 363: * However, must check ie_object to verify this, ! 364: * because collisions can happen. In case of a collision, ! 365: * search farther along in the clump. ! 366: */ ! 367: ! 368: while ((index = table[hindex].ie_index) != 0) { ! 369: ipc_entry_t entry = &table[index]; ! 370: ! 371: if (entry->ie_object == obj) { ! 372: *namep = MACH_PORT_MAKEB(index, entry->ie_bits); ! 373: *entryp = entry; ! 374: return TRUE; ! 375: } ! 376: ! 377: if (++hindex == size) ! 378: hindex = 0; ! 379: } ! 380: ! 381: return FALSE; ! 382: } ! 383: ! 384: /* ! 385: * Routine: ipc_hash_local_insert ! 386: * Purpose: ! 387: * Inserts an entry into the space's reverse hash table. ! 388: * Conditions: ! 389: * The space must be write-locked. ! 390: */ ! 391: ! 392: void ! 393: ipc_hash_local_insert( ! 394: ipc_space_t space, ! 395: ipc_object_t obj, ! 396: mach_port_index_t index, ! 397: ipc_entry_t entry) ! 398: { ! 399: ipc_entry_t table; ! 400: ipc_entry_num_t size; ! 401: mach_port_index_t hindex; ! 402: ! 403: assert(index != 0); ! 404: assert(space != IS_NULL); ! 405: assert(obj != IO_NULL); ! 406: ! 407: table = space->is_table; ! 408: size = space->is_table_size; ! 409: hindex = IH_LOCAL_HASH(obj, size); ! 410: ! 411: assert(entry == &table[index]); ! 412: assert(entry->ie_object == obj); ! 413: ! 414: /* ! 415: * We want to insert at hindex, but there may be collisions. ! 416: * If a collision occurs, search for the end of the clump ! 417: * and insert there. ! 418: */ ! 419: ! 420: while (table[hindex].ie_index != 0) { ! 421: if (++hindex == size) ! 422: hindex = 0; ! 423: } ! 424: ! 425: table[hindex].ie_index = index; ! 426: } ! 427: ! 428: /* ! 429: * Routine: ipc_hash_local_delete ! 430: * Purpose: ! 431: * Deletes an entry from the space's reverse hash table. ! 432: * Conditions: ! 433: * The space must be write-locked. ! 434: */ ! 435: ! 436: void ! 437: ipc_hash_local_delete( ! 438: ipc_space_t space, ! 439: ipc_object_t obj, ! 440: mach_port_index_t index, ! 441: ipc_entry_t entry) ! 442: { ! 443: ipc_entry_t table; ! 444: ipc_entry_num_t size; ! 445: mach_port_index_t hindex, dindex; ! 446: ! 447: assert(index != MACH_PORT_NULL); ! 448: assert(space != IS_NULL); ! 449: assert(obj != IO_NULL); ! 450: ! 451: table = space->is_table; ! 452: size = space->is_table_size; ! 453: hindex = IH_LOCAL_HASH(obj, size); ! 454: ! 455: assert(entry == &table[index]); ! 456: assert(entry->ie_object == obj); ! 457: ! 458: /* ! 459: * First check we have the right hindex for this index. ! 460: * In case of collision, we have to search farther ! 461: * along in this clump. ! 462: */ ! 463: ! 464: while (table[hindex].ie_index != index) { ! 465: if (table[hindex].ie_index == 0) ! 466: { ! 467: static int gak = 0; ! 468: if (gak == 0) ! 469: { ! 470: printf("gak! entry wasn't in hash table!\n"); ! 471: gak = 1; ! 472: } ! 473: return; ! 474: } ! 475: if (++hindex == size) ! 476: hindex = 0; ! 477: } ! 478: ! 479: /* ! 480: * Now we want to set table[hindex].ie_index = 0. ! 481: * But if we aren't the last index in a clump, ! 482: * this might cause problems for lookups of objects ! 483: * farther along in the clump that are displaced ! 484: * due to collisions. Searches for them would fail ! 485: * at hindex instead of succeeding. ! 486: * ! 487: * So we must check the clump after hindex for objects ! 488: * that are so displaced, and move one up to the new hole. ! 489: * ! 490: * hindex - index of new hole in the clump ! 491: * dindex - index we are checking for a displaced object ! 492: * ! 493: * When we move a displaced object up into the hole, ! 494: * it creates a new hole, and we have to repeat the process ! 495: * until we get to the end of the clump. ! 496: */ ! 497: ! 498: for (dindex = hindex; index != 0; hindex = dindex) { ! 499: for (;;) { ! 500: mach_port_index_t tindex; ! 501: ipc_object_t tobj; ! 502: ! 503: if (++dindex == size) ! 504: dindex = 0; ! 505: assert(dindex != hindex); ! 506: ! 507: /* are we at the end of the clump? */ ! 508: ! 509: index = table[dindex].ie_index; ! 510: if (index == 0) ! 511: break; ! 512: ! 513: /* is this a displaced object? */ ! 514: ! 515: tobj = table[index].ie_object; ! 516: assert(tobj != IO_NULL); ! 517: tindex = IH_LOCAL_HASH(tobj, size); ! 518: ! 519: if ((dindex < hindex) ? ! 520: ((dindex < tindex) && (tindex <= hindex)) : ! 521: ((dindex < tindex) || (tindex <= hindex))) ! 522: break; ! 523: } ! 524: ! 525: table[hindex].ie_index = index; ! 526: } ! 527: } ! 528: ! 529: /* ! 530: * Routine: ipc_hash_init ! 531: * Purpose: ! 532: * Initialize the reverse hash table implementation. ! 533: */ ! 534: ! 535: void ! 536: ipc_hash_init(void) ! 537: { ! 538: ipc_hash_index_t i; ! 539: ! 540: /* if not configured, initialize ipc_hash_global_size */ ! 541: ! 542: if (ipc_hash_global_size == 0) { ! 543: ipc_hash_global_size = ipc_tree_entry_max >> 8; ! 544: if (ipc_hash_global_size < 32) ! 545: ipc_hash_global_size = 32; ! 546: } ! 547: ! 548: /* make sure it is a power of two */ ! 549: ! 550: ipc_hash_global_mask = ipc_hash_global_size - 1; ! 551: if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) { ! 552: natural_t bit; ! 553: ! 554: /* round up to closest power of two */ ! 555: ! 556: for (bit = 1;; bit <<= 1) { ! 557: ipc_hash_global_mask |= bit; ! 558: ipc_hash_global_size = ipc_hash_global_mask + 1; ! 559: ! 560: if ((ipc_hash_global_size & ipc_hash_global_mask) == 0) ! 561: break; ! 562: } ! 563: } ! 564: ! 565: /* allocate ipc_hash_global_table */ ! 566: ! 567: ipc_hash_global_table = (ipc_hash_global_bucket_t) ! 568: kalloc((vm_size_t) (ipc_hash_global_size * ! 569: sizeof(struct ipc_hash_global_bucket))); ! 570: assert(ipc_hash_global_table != IHGB_NULL); ! 571: ! 572: /* and initialize it */ ! 573: ! 574: for (i = 0; i < ipc_hash_global_size; i++) { ! 575: ipc_hash_global_bucket_t bucket; ! 576: ! 577: bucket = &ipc_hash_global_table[i]; ! 578: ihgb_lock_init(bucket); ! 579: bucket->ihgb_head = ITE_NULL; ! 580: } ! 581: } ! 582: ! 583: #if MACH_IPC_DEBUG ! 584: ! 585: /* ! 586: * Routine: ipc_hash_info ! 587: * Purpose: ! 588: * Return information about the global reverse hash table. ! 589: * Fills the buffer with as much information as possible ! 590: * and returns the desired size of the buffer. ! 591: * Conditions: ! 592: * Nothing locked. The caller should provide ! 593: * possibly-pageable memory. ! 594: */ ! 595: ! 596: ! 597: ipc_hash_index_t ! 598: ipc_hash_info( ! 599: hash_info_bucket_t *info, ! 600: mach_msg_type_number_t count) ! 601: { ! 602: ipc_hash_index_t i; ! 603: ! 604: if (ipc_hash_global_size < count) ! 605: count = ipc_hash_global_size; ! 606: ! 607: for (i = 0; i < count; i++) { ! 608: ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i]; ! 609: unsigned int bucket_count = 0; ! 610: ipc_tree_entry_t entry; ! 611: ! 612: ihgb_lock(bucket); ! 613: for (entry = bucket->ihgb_head; ! 614: entry != ITE_NULL; ! 615: entry = entry->ite_next) ! 616: bucket_count++; ! 617: ihgb_unlock(bucket); ! 618: ! 619: /* don't touch pageable memory while holding locks */ ! 620: info[i].hib_count = bucket_count; ! 621: } ! 622: ! 623: return ipc_hash_global_size; ! 624: } ! 625: ! 626: #endif /* MACH_IPC_DEBUG */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.