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