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