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