![[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.