![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ipc_entry.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_entry.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: * Copyright (c) 1993,1994 The University of Utah and ! 5: * the Computer Systems Laboratory (CSL). ! 6: * All rights reserved. ! 7: * ! 8: * Permission to use, copy, modify and distribute this software and its ! 9: * documentation is hereby granted, provided that both the copyright ! 10: * notice and this permission notice appear in all copies of the ! 11: * software, derivative works or modified versions, and any portions ! 12: * thereof, and that both notices appear in supporting documentation. ! 13: * ! 14: * CARNEGIE MELLON, THE UNIVERSITY OF UTAH AND CSL ALLOW FREE USE OF ! 15: * THIS SOFTWARE IN ITS "AS IS" CONDITION, AND DISCLAIM ANY LIABILITY ! 16: * OF ANY KIND FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF ! 17: * THIS SOFTWARE. ! 18: * ! 19: * Carnegie Mellon requests users of this software to return to ! 20: * ! 21: * Software Distribution Coordinator or [email protected] ! 22: * School of Computer Science ! 23: * Carnegie Mellon University ! 24: * Pittsburgh PA 15213-3890 ! 25: * ! 26: * any improvements or extensions that they make and grant Carnegie Mellon ! 27: * the rights to redistribute these changes. ! 28: */ ! 29: /* ! 30: * File: ipc/ipc_entry.c ! 31: * Author: Rich Draves ! 32: * Date: 1989 ! 33: * ! 34: * Primitive functions to manipulate translation entries. ! 35: */ ! 36: ! 37: #include <mach/kern_return.h> ! 38: #include <mach/port.h> ! 39: #include <kern/assert.h> ! 40: #include <kern/sched_prim.h> ! 41: #include <kern/zalloc.h> ! 42: #include <ipc/port.h> ! 43: #include <ipc/ipc_types.h> ! 44: #include <ipc/ipc_entry.h> ! 45: #include <ipc/ipc_space.h> ! 46: #include <ipc/ipc_splay.h> ! 47: #include <ipc/ipc_hash.h> ! 48: #include <ipc/ipc_table.h> ! 49: #include <ipc/ipc_object.h> ! 50: ! 51: zone_t ipc_tree_entry_zone; ! 52: ! 53: /* ! 54: * Routine: ipc_entry_tree_collision ! 55: * Purpose: ! 56: * Checks if "name" collides with an allocated name ! 57: * in the space's tree. That is, returns TRUE ! 58: * if the splay tree contains a name with the same ! 59: * index as "name". ! 60: * Conditions: ! 61: * The space is locked (read or write) and active. ! 62: */ ! 63: ! 64: boolean_t ! 65: ipc_entry_tree_collision( ! 66: ipc_space_t space, ! 67: mach_port_t name) ! 68: { ! 69: mach_port_index_t index; ! 70: mach_port_t lower, upper; ! 71: ! 72: assert(space->is_active); ! 73: ! 74: /* ! 75: * Check if we collide with the next smaller name ! 76: * or the next larger name. ! 77: */ ! 78: ! 79: ipc_splay_tree_bounds(&space->is_tree, name, &lower, &upper); ! 80: ! 81: index = MACH_PORT_INDEX(name); ! 82: return (((lower != ~0) && (MACH_PORT_INDEX(lower) == index)) || ! 83: ((upper != 0) && (MACH_PORT_INDEX(upper) == index))); ! 84: } ! 85: ! 86: /* ! 87: * Routine: ipc_entry_lookup ! 88: * Purpose: ! 89: * Searches for an entry, given its name. ! 90: * Conditions: ! 91: * The space must be read or write locked throughout. ! 92: * The space must be active. ! 93: */ ! 94: ! 95: ipc_entry_t ! 96: ipc_entry_lookup(space, name) ! 97: ipc_space_t space; ! 98: mach_port_t name; ! 99: { ! 100: mach_port_index_t index; ! 101: ipc_entry_t entry; ! 102: ! 103: assert(space->is_active); ! 104: ! 105: index = MACH_PORT_INDEX(name); ! 106: if (index < space->is_table_size) { ! 107: entry = &space->is_table[index]; ! 108: if (IE_BITS_GEN(entry->ie_bits) != MACH_PORT_GEN(name)) ! 109: if (entry->ie_bits & IE_BITS_COLLISION) { ! 110: assert(space->is_tree_total > 0); ! 111: goto tree_lookup; ! 112: } else ! 113: entry = IE_NULL; ! 114: else if (IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_NONE) ! 115: entry = IE_NULL; ! 116: } else if (space->is_tree_total == 0) ! 117: entry = IE_NULL; ! 118: else ! 119: tree_lookup: ! 120: entry = (ipc_entry_t) ! 121: ipc_splay_tree_lookup(&space->is_tree, name); ! 122: ! 123: assert((entry == IE_NULL) || IE_BITS_TYPE(entry->ie_bits)); ! 124: return entry; ! 125: } ! 126: ! 127: /* ! 128: * Routine: ipc_entry_get ! 129: * Purpose: ! 130: * Tries to allocate an entry out of the space. ! 131: * Conditions: ! 132: * The space is write-locked and active throughout. ! 133: * An object may be locked. Will not allocate memory. ! 134: * Returns: ! 135: * KERN_SUCCESS A free entry was found. ! 136: * KERN_NO_SPACE No entry allocated. ! 137: */ ! 138: ! 139: kern_return_t ! 140: ipc_entry_get(space, namep, entryp) ! 141: ipc_space_t space; ! 142: mach_port_t *namep; ! 143: ipc_entry_t *entryp; ! 144: { ! 145: ipc_entry_t table; ! 146: mach_port_index_t first_free; ! 147: mach_port_t new_name; ! 148: ipc_entry_t free_entry; ! 149: ! 150: assert(space->is_active); ! 151: ! 152: table = space->is_table; ! 153: first_free = table->ie_next; ! 154: ! 155: if (first_free == 0) ! 156: return KERN_NO_SPACE; ! 157: ! 158: free_entry = &table[first_free]; ! 159: table->ie_next = free_entry->ie_next; ! 160: ! 161: /* ! 162: * Initialize the new entry. We need only ! 163: * increment the generation number and clear ie_request. ! 164: */ ! 165: ! 166: { ! 167: mach_port_gen_t gen; ! 168: ! 169: assert((free_entry->ie_bits &~ IE_BITS_GEN_MASK) == 0); ! 170: gen = free_entry->ie_bits + IE_BITS_GEN_ONE; ! 171: free_entry->ie_bits = gen; ! 172: free_entry->ie_request = 0; ! 173: new_name = MACH_PORT_MAKE(first_free, gen); ! 174: } ! 175: ! 176: /* ! 177: * The new name can't be MACH_PORT_NULL because index ! 178: * is non-zero. It can't be MACH_PORT_DEAD because ! 179: * the table isn't allowed to grow big enough. ! 180: * (See comment in ipc/ipc_table.h.) ! 181: */ ! 182: ! 183: assert(MACH_PORT_VALID(new_name)); ! 184: assert(free_entry->ie_object == IO_NULL); ! 185: ! 186: *namep = new_name; ! 187: *entryp = free_entry; ! 188: return KERN_SUCCESS; ! 189: } ! 190: ! 191: /* ! 192: * Routine: ipc_entry_alloc ! 193: * Purpose: ! 194: * Allocate an entry out of the space. ! 195: * Conditions: ! 196: * The space is not locked before, but it is write-locked after ! 197: * if the call is successful. May allocate memory. ! 198: * Returns: ! 199: * KERN_SUCCESS An entry was allocated. ! 200: * KERN_INVALID_TASK The space is dead. ! 201: * KERN_NO_SPACE No room for an entry in the space. ! 202: * KERN_RESOURCE_SHORTAGE Couldn't allocate memory for an entry. ! 203: */ ! 204: ! 205: kern_return_t ! 206: ipc_entry_alloc( ! 207: ipc_space_t space, ! 208: mach_port_t *namep, ! 209: ipc_entry_t *entryp) ! 210: { ! 211: kern_return_t kr; ! 212: ! 213: is_write_lock(space); ! 214: ! 215: for (;;) { ! 216: if (!space->is_active) { ! 217: is_write_unlock(space); ! 218: return KERN_INVALID_TASK; ! 219: } ! 220: ! 221: kr = ipc_entry_get(space, namep, entryp); ! 222: if (kr == KERN_SUCCESS) ! 223: return kr; ! 224: ! 225: kr = ipc_entry_grow_table(space); ! 226: if (kr != KERN_SUCCESS) ! 227: return kr; /* space is unlocked */ ! 228: } ! 229: } ! 230: ! 231: /* ! 232: * Routine: ipc_entry_alloc_name ! 233: * Purpose: ! 234: * Allocates/finds an entry with a specific name. ! 235: * If an existing entry is returned, its type will be nonzero. ! 236: * Conditions: ! 237: * The space is not locked before, but it is write-locked after ! 238: * if the call is successful. May allocate memory. ! 239: * Returns: ! 240: * KERN_SUCCESS Found existing entry with same name. ! 241: * KERN_SUCCESS Allocated a new entry. ! 242: * KERN_INVALID_TASK The space is dead. ! 243: * KERN_RESOURCE_SHORTAGE Couldn't allocate memory. ! 244: */ ! 245: ! 246: kern_return_t ! 247: ipc_entry_alloc_name( ! 248: ipc_space_t space, ! 249: mach_port_t name, ! 250: ipc_entry_t *entryp) ! 251: { ! 252: mach_port_index_t index = MACH_PORT_INDEX(name); ! 253: mach_port_gen_t gen = MACH_PORT_GEN(name); ! 254: ipc_tree_entry_t tree_entry = ITE_NULL; ! 255: ! 256: assert(MACH_PORT_VALID(name)); ! 257: ! 258: ! 259: is_write_lock(space); ! 260: ! 261: for (;;) { ! 262: ipc_entry_t entry; ! 263: ipc_tree_entry_t tentry; ! 264: ipc_table_size_t its; ! 265: ! 266: if (!space->is_active) { ! 267: is_write_unlock(space); ! 268: if (tree_entry) ite_free(tree_entry); ! 269: return KERN_INVALID_TASK; ! 270: } ! 271: ! 272: /* ! 273: * If we are under the table cutoff, ! 274: * there are three cases: ! 275: * 1) The entry is inuse, for the same name ! 276: * 2) The entry is inuse, for a different name ! 277: * 3) The entry is free ! 278: */ ! 279: ! 280: if ((0 < index) && (index < space->is_table_size)) { ! 281: ipc_entry_t table = space->is_table; ! 282: ! 283: entry = &table[index]; ! 284: ! 285: if (IE_BITS_TYPE(entry->ie_bits)) { ! 286: if (IE_BITS_GEN(entry->ie_bits) == gen) { ! 287: *entryp = entry; ! 288: if (tree_entry) ite_free(tree_entry); ! 289: return KERN_SUCCESS; ! 290: } ! 291: } else { ! 292: mach_port_index_t free_index, next_index; ! 293: ! 294: /* ! 295: * Rip the entry out of the free list. ! 296: */ ! 297: ! 298: for (free_index = 0; ! 299: (next_index = table[free_index].ie_next) ! 300: != index; ! 301: free_index = next_index) ! 302: continue; ! 303: ! 304: table[free_index].ie_next = ! 305: table[next_index].ie_next; ! 306: ! 307: entry->ie_bits = gen; ! 308: assert(entry->ie_object == IO_NULL); ! 309: entry->ie_request = 0; ! 310: ! 311: *entryp = entry; ! 312: if (tree_entry) ite_free(tree_entry); ! 313: return KERN_SUCCESS; ! 314: } ! 315: } ! 316: ! 317: /* ! 318: * Before trying to allocate any memory, ! 319: * check if the entry already exists in the tree. ! 320: * This avoids spurious resource errors. ! 321: * The splay tree makes a subsequent lookup/insert ! 322: * of the same name cheap, so this costs little. ! 323: */ ! 324: ! 325: if ((space->is_tree_total > 0) && ! 326: ((tentry = ipc_splay_tree_lookup(&space->is_tree, name)) ! 327: != ITE_NULL)) { ! 328: assert(tentry->ite_space == space); ! 329: assert(IE_BITS_TYPE(tentry->ite_bits)); ! 330: ! 331: *entryp = &tentry->ite_entry; ! 332: if (tree_entry) ite_free(tree_entry); ! 333: return KERN_SUCCESS; ! 334: } ! 335: ! 336: its = space->is_table_next; ! 337: ! 338: /* ! 339: * Check if the table should be grown. ! 340: * ! 341: * Note that if space->is_table_size == its->its_size, ! 342: * then we won't ever try to grow the table. ! 343: * ! 344: * Note that we are optimistically assuming that name ! 345: * doesn't collide with any existing names. (So if ! 346: * it were entered into the tree, is_tree_small would ! 347: * be incremented.) This is OK, because even in that ! 348: * case, we don't lose memory by growing the table. ! 349: */ ! 350: ! 351: if ((space->is_table_size <= index) && ! 352: (index < its->its_size) && ! 353: (((its->its_size - space->is_table_size) * ! 354: sizeof(struct ipc_entry)) < ! 355: ((space->is_tree_small + 1) * ! 356: sizeof(struct ipc_tree_entry)))) { ! 357: kern_return_t kr; ! 358: ! 359: /* ! 360: * Can save space by growing the table. ! 361: * Because the space will be unlocked, ! 362: * we must restart. ! 363: */ ! 364: ! 365: kr = ipc_entry_grow_table(space); ! 366: assert(kr != KERN_NO_SPACE); ! 367: if (kr != KERN_SUCCESS) { ! 368: /* space is unlocked */ ! 369: if (tree_entry) ite_free(tree_entry); ! 370: return kr; ! 371: } ! 372: ! 373: continue; ! 374: } ! 375: ! 376: /* ! 377: * If a splay-tree entry was allocated previously, ! 378: * go ahead and insert it into the tree. ! 379: */ ! 380: ! 381: if (tree_entry != ITE_NULL) { ! 382: space->is_tree_total++; ! 383: ! 384: if (index < space->is_table_size) ! 385: space->is_table[index].ie_bits |= ! 386: IE_BITS_COLLISION; ! 387: else if ((index < its->its_size) && ! 388: !ipc_entry_tree_collision(space, name)) ! 389: space->is_tree_small++; ! 390: ! 391: ipc_splay_tree_insert(&space->is_tree, ! 392: name, tree_entry); ! 393: ! 394: tree_entry->ite_bits = 0; ! 395: tree_entry->ite_object = IO_NULL; ! 396: tree_entry->ite_request = 0; ! 397: tree_entry->ite_space = space; ! 398: *entryp = &tree_entry->ite_entry; ! 399: return KERN_SUCCESS; ! 400: } ! 401: ! 402: /* ! 403: * Allocate a tree entry and try again. ! 404: */ ! 405: ! 406: is_write_unlock(space); ! 407: tree_entry = ite_alloc(); ! 408: if (tree_entry == ITE_NULL) ! 409: return KERN_RESOURCE_SHORTAGE; ! 410: is_write_lock(space); ! 411: } ! 412: } ! 413: ! 414: /* ! 415: * Routine: ipc_entry_dealloc ! 416: * Purpose: ! 417: * Deallocates an entry from a space. ! 418: * Conditions: ! 419: * The space must be write-locked throughout. ! 420: * The space must be active. ! 421: */ ! 422: ! 423: void ! 424: ipc_entry_dealloc( ! 425: ipc_space_t space, ! 426: mach_port_t name, ! 427: ipc_entry_t entry) ! 428: { ! 429: ipc_entry_t table; ! 430: ipc_entry_num_t size; ! 431: mach_port_index_t index; ! 432: ! 433: assert(space->is_active); ! 434: assert(entry->ie_object == IO_NULL); ! 435: assert(entry->ie_request == 0); ! 436: ! 437: index = MACH_PORT_INDEX(name); ! 438: table = space->is_table; ! 439: size = space->is_table_size; ! 440: ! 441: if ((index < size) && (entry == &table[index])) { ! 442: assert(IE_BITS_GEN(entry->ie_bits) == MACH_PORT_GEN(name)); ! 443: ! 444: if (entry->ie_bits & IE_BITS_COLLISION) { ! 445: struct ipc_splay_tree small, collisions; ! 446: ipc_tree_entry_t tentry; ! 447: mach_port_t tname; ! 448: boolean_t pick; ! 449: ipc_entry_bits_t bits; ! 450: ipc_object_t obj; ! 451: ! 452: /* must move an entry from tree to table */ ! 453: ! 454: ipc_splay_tree_split(&space->is_tree, ! 455: MACH_PORT_MAKE(index+1, 0), ! 456: &collisions); ! 457: ipc_splay_tree_split(&collisions, ! 458: MACH_PORT_MAKE(index, 0), ! 459: &small); ! 460: ! 461: pick = ipc_splay_tree_pick(&collisions, ! 462: &tname, &tentry); ! 463: assert(pick); ! 464: assert(MACH_PORT_INDEX(tname) == index); ! 465: ! 466: bits = tentry->ite_bits; ! 467: entry->ie_bits = bits | MACH_PORT_GEN(tname); ! 468: entry->ie_object = obj = tentry->ite_object; ! 469: entry->ie_request = tentry->ite_request; ! 470: assert(tentry->ite_space == space); ! 471: ! 472: if (IE_BITS_TYPE(bits) == MACH_PORT_TYPE_SEND) { ! 473: ipc_hash_global_delete(space, obj, ! 474: tname, tentry); ! 475: ipc_hash_local_insert(space, obj, ! 476: index, entry); ! 477: } ! 478: ! 479: ipc_splay_tree_delete(&collisions, tname, tentry); ! 480: ! 481: assert(space->is_tree_total > 0); ! 482: space->is_tree_total--; ! 483: ! 484: /* check if collision bit should still be on */ ! 485: ! 486: pick = ipc_splay_tree_pick(&collisions, ! 487: &tname, &tentry); ! 488: if (pick) { ! 489: entry->ie_bits |= IE_BITS_COLLISION; ! 490: ipc_splay_tree_join(&space->is_tree, ! 491: &collisions); ! 492: } ! 493: ! 494: ipc_splay_tree_join(&space->is_tree, &small); ! 495: } else { ! 496: entry->ie_bits &= IE_BITS_GEN_MASK; ! 497: entry->ie_next = table->ie_next; ! 498: table->ie_next = index; ! 499: } ! 500: } else { ! 501: ipc_tree_entry_t tentry = (ipc_tree_entry_t) entry; ! 502: ! 503: assert(tentry->ite_space == space); ! 504: ! 505: ipc_splay_tree_delete(&space->is_tree, name, tentry); ! 506: ! 507: assert(space->is_tree_total > 0); ! 508: space->is_tree_total--; ! 509: ! 510: if (index < size) { ! 511: ipc_entry_t ientry = &table[index]; ! 512: ! 513: assert(ientry->ie_bits & IE_BITS_COLLISION); ! 514: ! 515: if (!ipc_entry_tree_collision(space, name)) ! 516: ientry->ie_bits &= ~IE_BITS_COLLISION; ! 517: } else if ((index < space->is_table_next->its_size) && ! 518: !ipc_entry_tree_collision(space, name)) { ! 519: assert(space->is_tree_small > 0); ! 520: space->is_tree_small--; ! 521: } ! 522: } ! 523: } ! 524: ! 525: /* ! 526: * Routine: ipc_entry_grow_table ! 527: * Purpose: ! 528: * Grows the table in a space. ! 529: * Conditions: ! 530: * The space must be write-locked and active before. ! 531: * If successful, it is also returned locked. ! 532: * Allocates memory. ! 533: * Returns: ! 534: * KERN_SUCCESS Grew the table. ! 535: * KERN_SUCCESS Somebody else grew the table. ! 536: * KERN_SUCCESS The space died. ! 537: * KERN_NO_SPACE Table has maximum size already. ! 538: * KERN_RESOURCE_SHORTAGE Couldn't allocate a new table. ! 539: */ ! 540: ! 541: kern_return_t ! 542: ipc_entry_grow_table(space) ! 543: ipc_space_t space; ! 544: { ! 545: ipc_entry_num_t osize, size, nsize; ! 546: ! 547: do { ! 548: ipc_entry_t otable, table; ! 549: ipc_table_size_t oits, its, nits; ! 550: mach_port_index_t i, free_index; ! 551: ! 552: assert(space->is_active); ! 553: ! 554: if (space->is_growing) { ! 555: /* ! 556: * Somebody else is growing the table. ! 557: * We just wait for them to finish. ! 558: */ ! 559: ! 560: assert_wait((event_t) space, FALSE); ! 561: is_write_unlock(space); ! 562: thread_block((void (*)()) 0); ! 563: is_write_lock(space); ! 564: return KERN_SUCCESS; ! 565: } ! 566: ! 567: otable = space->is_table; ! 568: its = space->is_table_next; ! 569: size = its->its_size; ! 570: oits = its - 1; ! 571: osize = oits->its_size; ! 572: nits = its + 1; ! 573: nsize = nits->its_size; ! 574: ! 575: if (osize == size) { ! 576: is_write_unlock(space); ! 577: return KERN_NO_SPACE; ! 578: } ! 579: ! 580: assert((osize < size) && (size <= nsize)); ! 581: ! 582: /* ! 583: * OK, we'll attempt to grow the table. ! 584: * The realloc requires that the old table ! 585: * remain in existence. ! 586: */ ! 587: ! 588: space->is_growing = TRUE; ! 589: is_write_unlock(space); ! 590: if (it_entries_reallocable(oits)) ! 591: table = it_entries_realloc(oits, otable, its); ! 592: else ! 593: table = it_entries_alloc(its); ! 594: is_write_lock(space); ! 595: space->is_growing = FALSE; ! 596: ! 597: /* ! 598: * We need to do a wakeup on the space, ! 599: * to rouse waiting threads. We defer ! 600: * this until the space is unlocked, ! 601: * because we don't want them to spin. ! 602: */ ! 603: ! 604: if (table == IE_NULL) { ! 605: is_write_unlock(space); ! 606: thread_wakeup((event_t) space); ! 607: return KERN_RESOURCE_SHORTAGE; ! 608: } ! 609: ! 610: if (!space->is_active) { ! 611: /* ! 612: * The space died while it was unlocked. ! 613: */ ! 614: ! 615: is_write_unlock(space); ! 616: thread_wakeup((event_t) space); ! 617: it_entries_free(its, table); ! 618: is_write_lock(space); ! 619: return KERN_SUCCESS; ! 620: } ! 621: ! 622: assert(space->is_table == otable); ! 623: assert(space->is_table_next == its); ! 624: assert(space->is_table_size == osize); ! 625: ! 626: space->is_table = table; ! 627: space->is_table_size = size; ! 628: space->is_table_next = nits; ! 629: ! 630: /* ! 631: * If we did a realloc, it remapped the data. ! 632: * Otherwise we copy by hand first. Then we have ! 633: * to clear the index fields in the old part and ! 634: * zero the new part. ! 635: */ ! 636: ! 637: if (!it_entries_reallocable(oits)) ! 638: (void) memcpy((void *) table, (const void *) otable, ! 639: osize * sizeof(struct ipc_entry)); ! 640: ! 641: for (i = 0; i < osize; i++) ! 642: table[i].ie_index = 0; ! 643: ! 644: (void) memset((void *) (table + osize), 0, ! 645: (size - osize) * sizeof(struct ipc_entry)); ! 646: ! 647: /* ! 648: * Put old entries into the reverse hash table. ! 649: */ ! 650: ! 651: for (i = 0; i < osize; i++) { ! 652: ipc_entry_t entry = &table[i]; ! 653: ! 654: if (IE_BITS_TYPE(entry->ie_bits) == ! 655: MACH_PORT_TYPE_SEND) ! 656: ipc_hash_local_insert(space, entry->ie_object, ! 657: i, entry); ! 658: } ! 659: ! 660: /* ! 661: * If there are entries in the splay tree, ! 662: * then we have work to do: ! 663: * 1) transfer entries to the table ! 664: * 2) update is_tree_small ! 665: */ ! 666: ! 667: if (space->is_tree_total > 0) { ! 668: mach_port_index_t index; ! 669: boolean_t delete; ! 670: struct ipc_splay_tree ignore; ! 671: struct ipc_splay_tree move; ! 672: struct ipc_splay_tree small; ! 673: ipc_entry_num_t nosmall; ! 674: ipc_tree_entry_t tentry; ! 675: ! 676: /* ! 677: * The splay tree divides into four regions, ! 678: * based on the index of the entries: ! 679: * 1) 0 <= index < osize ! 680: * 2) osize <= index < size ! 681: * 3) size <= index < nsize ! 682: * 4) nsize <= index ! 683: * ! 684: * Entries in the first part are ignored. ! 685: * Entries in the second part, that don't ! 686: * collide, are moved into the table. ! 687: * Entries in the third part, that don't ! 688: * collide, are counted for is_tree_small. ! 689: * Entries in the fourth part are ignored. ! 690: */ ! 691: ! 692: ipc_splay_tree_split(&space->is_tree, ! 693: MACH_PORT_MAKE(nsize, 0), ! 694: &small); ! 695: ipc_splay_tree_split(&small, ! 696: MACH_PORT_MAKE(size, 0), ! 697: &move); ! 698: ipc_splay_tree_split(&move, ! 699: MACH_PORT_MAKE(osize, 0), ! 700: &ignore); ! 701: ! 702: /* move entries into the table */ ! 703: ! 704: for (tentry = ipc_splay_traverse_start(&move); ! 705: tentry != ITE_NULL; ! 706: tentry = ipc_splay_traverse_next(&move, delete)) { ! 707: mach_port_t name; ! 708: mach_port_gen_t gen; ! 709: mach_port_type_t type; ! 710: ipc_entry_bits_t bits; ! 711: ipc_object_t obj; ! 712: ipc_entry_t entry; ! 713: ! 714: name = tentry->ite_name; ! 715: gen = MACH_PORT_GEN(name); ! 716: index = MACH_PORT_INDEX(name); ! 717: ! 718: assert(tentry->ite_space == space); ! 719: assert((osize <= index) && (index < size)); ! 720: ! 721: entry = &table[index]; ! 722: ! 723: /* collision with previously moved entry? */ ! 724: ! 725: bits = entry->ie_bits; ! 726: if (bits != 0) { ! 727: assert(IE_BITS_TYPE(bits)); ! 728: assert(IE_BITS_GEN(bits) != gen); ! 729: ! 730: entry->ie_bits = ! 731: bits | IE_BITS_COLLISION; ! 732: delete = FALSE; ! 733: continue; ! 734: } ! 735: ! 736: bits = tentry->ite_bits; ! 737: type = IE_BITS_TYPE(bits); ! 738: assert(type != MACH_PORT_TYPE_NONE); ! 739: ! 740: entry->ie_bits = bits | gen; ! 741: entry->ie_object = obj = tentry->ite_object; ! 742: entry->ie_request = tentry->ite_request; ! 743: ! 744: if (type == MACH_PORT_TYPE_SEND) { ! 745: ipc_hash_global_delete(space, obj, ! 746: name, tentry); ! 747: ipc_hash_local_insert(space, obj, ! 748: index, entry); ! 749: } ! 750: ! 751: space->is_tree_total--; ! 752: delete = TRUE; ! 753: } ! 754: ipc_splay_traverse_finish(&move); ! 755: ! 756: /* count entries for is_tree_small */ ! 757: ! 758: nosmall = 0; index = 0; ! 759: for (tentry = ipc_splay_traverse_start(&small); ! 760: tentry != ITE_NULL; ! 761: tentry = ipc_splay_traverse_next(&small, FALSE)) { ! 762: mach_port_index_t nindex; ! 763: ! 764: nindex = MACH_PORT_INDEX(tentry->ite_name); ! 765: ! 766: if (nindex != index) { ! 767: nosmall++; ! 768: index = nindex; ! 769: } ! 770: } ! 771: ipc_splay_traverse_finish(&small); ! 772: ! 773: assert(nosmall <= (nsize - size)); ! 774: assert(nosmall <= space->is_tree_total); ! 775: space->is_tree_small = nosmall; ! 776: ! 777: /* put the splay tree back together */ ! 778: ! 779: ipc_splay_tree_join(&space->is_tree, &small); ! 780: ipc_splay_tree_join(&space->is_tree, &move); ! 781: ipc_splay_tree_join(&space->is_tree, &ignore); ! 782: } ! 783: ! 784: /* ! 785: * Add entries in the new part which still aren't used ! 786: * to the free list. Add them in reverse order, ! 787: * and set the generation number to -1, so that ! 788: * early allocations produce "natural" names. ! 789: */ ! 790: ! 791: free_index = table[0].ie_next; ! 792: for (i = size-1; i >= osize; --i) { ! 793: ipc_entry_t entry = &table[i]; ! 794: ! 795: if (entry->ie_bits == 0) { ! 796: entry->ie_bits = IE_BITS_GEN_MASK; ! 797: entry->ie_next = free_index; ! 798: free_index = i; ! 799: } ! 800: } ! 801: table[0].ie_next = free_index; ! 802: ! 803: /* ! 804: * Now we need to free the old table. ! 805: * If the space dies or grows while unlocked, ! 806: * then we can quit here. ! 807: */ ! 808: ! 809: is_write_unlock(space); ! 810: thread_wakeup((event_t) space); ! 811: it_entries_free(oits, otable); ! 812: is_write_lock(space); ! 813: if (!space->is_active || (space->is_table_next != nits)) ! 814: return KERN_SUCCESS; ! 815: ! 816: /* ! 817: * We might have moved enough entries from ! 818: * the splay tree into the table that ! 819: * the table can be profitably grown again. ! 820: * ! 821: * Note that if size == nsize, then ! 822: * space->is_tree_small == 0. ! 823: */ ! 824: } while ((space->is_tree_small > 0) && ! 825: (((nsize - size) * sizeof(struct ipc_entry)) < ! 826: (space->is_tree_small * sizeof(struct ipc_tree_entry)))); ! 827: ! 828: return KERN_SUCCESS; ! 829: } ! 830: ! 831: ! 832: #if MACH_KDB ! 833: #include <ddb/db_output.h> ! 834: #include <kern/task.h> ! 835: ! 836: #define printf kdbprintf ! 837: ! 838: ipc_entry_t db_ipc_object_by_name( ! 839: task_t task, ! 840: mach_port_t name); ! 841: ! 842: ! 843: ipc_entry_t ! 844: db_ipc_object_by_name( ! 845: task_t task, ! 846: mach_port_t name) ! 847: { ! 848: ipc_space_t space = task->itk_space; ! 849: ipc_entry_t entry; ! 850: ! 851: ! 852: entry = ipc_entry_lookup(space, name); ! 853: if(entry != IE_NULL) { ! 854: iprintf("(task 0x%x, name 0x%x) ==> object 0x%x", ! 855: entry->ie_object); ! 856: return (ipc_entry_t) entry->ie_object; ! 857: } ! 858: return entry; ! 859: } ! 860: #endif /* MACH_KDB */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.