![[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
99: ipc_entry_lookup(space, name)
100: ipc_space_t space;
101: mach_port_t name;
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
143: ipc_entry_get(space, namep, entryp)
144: ipc_space_t space;
145: mach_port_t *namep;
146: ipc_entry_t *entryp;
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
545: ipc_entry_grow_table(space)
546: ipc_space_t space;
547: {
548: ipc_entry_num_t osize, size, nsize;
549:
550: do {
551: ipc_entry_t otable, table;
552: ipc_table_size_t oits, its, nits;
553: mach_port_index_t i, free_index;
554:
555: assert(space->is_active);
556:
557: if (space->is_growing) {
558: /*
559: * Somebody else is growing the table.
560: * We just wait for them to finish.
561: */
562:
563: assert_wait((event_t) space, FALSE);
564: is_write_unlock(space);
565: thread_block((void (*)()) 0);
566: is_write_lock(space);
567: return KERN_SUCCESS;
568: }
569:
570: otable = space->is_table;
571: its = space->is_table_next;
572: size = its->its_size;
573: oits = its - 1;
574: osize = oits->its_size;
575: nits = its + 1;
576: nsize = nits->its_size;
577:
578: if (osize == size) {
579: is_write_unlock(space);
1.1.1.3 ! root 580: printf_once("no more room for ipc_entry_grow_table in space %p\n", space);
1.1 root 581: return KERN_NO_SPACE;
582: }
583:
584: assert((osize < size) && (size <= nsize));
585:
586: /*
587: * OK, we'll attempt to grow the table.
588: * The realloc requires that the old table
589: * remain in existence.
590: */
591:
592: space->is_growing = TRUE;
593: is_write_unlock(space);
594: if (it_entries_reallocable(oits))
595: table = it_entries_realloc(oits, otable, its);
596: else
597: table = it_entries_alloc(its);
598: is_write_lock(space);
599: space->is_growing = FALSE;
600:
601: /*
602: * We need to do a wakeup on the space,
603: * to rouse waiting threads. We defer
604: * this until the space is unlocked,
605: * because we don't want them to spin.
606: */
607:
608: if (table == IE_NULL) {
609: is_write_unlock(space);
610: thread_wakeup((event_t) space);
611: return KERN_RESOURCE_SHORTAGE;
612: }
613:
614: if (!space->is_active) {
615: /*
616: * The space died while it was unlocked.
617: */
618:
619: is_write_unlock(space);
620: thread_wakeup((event_t) space);
621: it_entries_free(its, table);
622: is_write_lock(space);
623: return KERN_SUCCESS;
624: }
625:
626: assert(space->is_table == otable);
627: assert(space->is_table_next == its);
628: assert(space->is_table_size == osize);
629:
630: space->is_table = table;
631: space->is_table_size = size;
632: space->is_table_next = nits;
633:
634: /*
635: * If we did a realloc, it remapped the data.
636: * Otherwise we copy by hand first. Then we have
637: * to clear the index fields in the old part and
638: * zero the new part.
639: */
640:
641: if (!it_entries_reallocable(oits))
1.1.1.3 ! root 642: memcpy(table, otable,
1.1 root 643: osize * sizeof(struct ipc_entry));
644:
645: for (i = 0; i < osize; i++)
646: table[i].ie_index = 0;
647:
648: (void) memset((void *) (table + osize), 0,
649: (size - osize) * sizeof(struct ipc_entry));
650:
651: /*
652: * Put old entries into the reverse hash table.
653: */
654:
655: for (i = 0; i < osize; i++) {
656: ipc_entry_t entry = &table[i];
657:
658: if (IE_BITS_TYPE(entry->ie_bits) ==
659: MACH_PORT_TYPE_SEND)
660: ipc_hash_local_insert(space, entry->ie_object,
661: i, entry);
662: }
663:
664: /*
665: * If there are entries in the splay tree,
666: * then we have work to do:
667: * 1) transfer entries to the table
668: * 2) update is_tree_small
669: */
670:
671: if (space->is_tree_total > 0) {
672: mach_port_index_t index;
673: boolean_t delete;
674: struct ipc_splay_tree ignore;
675: struct ipc_splay_tree move;
676: struct ipc_splay_tree small;
677: ipc_entry_num_t nosmall;
678: ipc_tree_entry_t tentry;
679:
680: /*
681: * The splay tree divides into four regions,
682: * based on the index of the entries:
683: * 1) 0 <= index < osize
684: * 2) osize <= index < size
685: * 3) size <= index < nsize
686: * 4) nsize <= index
687: *
688: * Entries in the first part are ignored.
689: * Entries in the second part, that don't
690: * collide, are moved into the table.
691: * Entries in the third part, that don't
692: * collide, are counted for is_tree_small.
693: * Entries in the fourth part are ignored.
694: */
695:
696: ipc_splay_tree_split(&space->is_tree,
697: MACH_PORT_MAKE(nsize, 0),
698: &small);
699: ipc_splay_tree_split(&small,
700: MACH_PORT_MAKE(size, 0),
701: &move);
702: ipc_splay_tree_split(&move,
703: MACH_PORT_MAKE(osize, 0),
704: &ignore);
705:
706: /* move entries into the table */
707:
708: for (tentry = ipc_splay_traverse_start(&move);
709: tentry != ITE_NULL;
710: tentry = ipc_splay_traverse_next(&move, delete)) {
711: mach_port_t name;
712: mach_port_gen_t gen;
713: mach_port_type_t type;
714: ipc_entry_bits_t bits;
715: ipc_object_t obj;
716: ipc_entry_t entry;
717:
718: name = tentry->ite_name;
719: gen = MACH_PORT_GEN(name);
720: index = MACH_PORT_INDEX(name);
721:
722: assert(tentry->ite_space == space);
723: assert((osize <= index) && (index < size));
724:
725: entry = &table[index];
726:
727: /* collision with previously moved entry? */
728:
729: bits = entry->ie_bits;
730: if (bits != 0) {
731: assert(IE_BITS_TYPE(bits));
732: assert(IE_BITS_GEN(bits) != gen);
733:
734: entry->ie_bits =
735: bits | IE_BITS_COLLISION;
736: delete = FALSE;
737: continue;
738: }
739:
740: bits = tentry->ite_bits;
741: type = IE_BITS_TYPE(bits);
742: assert(type != MACH_PORT_TYPE_NONE);
743:
744: entry->ie_bits = bits | gen;
745: entry->ie_object = obj = tentry->ite_object;
746: entry->ie_request = tentry->ite_request;
747:
748: if (type == MACH_PORT_TYPE_SEND) {
749: ipc_hash_global_delete(space, obj,
750: name, tentry);
751: ipc_hash_local_insert(space, obj,
752: index, entry);
753: }
754:
755: space->is_tree_total--;
756: delete = TRUE;
757: }
758: ipc_splay_traverse_finish(&move);
759:
760: /* count entries for is_tree_small */
761:
762: nosmall = 0; index = 0;
763: for (tentry = ipc_splay_traverse_start(&small);
764: tentry != ITE_NULL;
765: tentry = ipc_splay_traverse_next(&small, FALSE)) {
766: mach_port_index_t nindex;
767:
768: nindex = MACH_PORT_INDEX(tentry->ite_name);
769:
770: if (nindex != index) {
771: nosmall++;
772: index = nindex;
773: }
774: }
775: ipc_splay_traverse_finish(&small);
776:
777: assert(nosmall <= (nsize - size));
778: assert(nosmall <= space->is_tree_total);
779: space->is_tree_small = nosmall;
780:
781: /* put the splay tree back together */
782:
783: ipc_splay_tree_join(&space->is_tree, &small);
784: ipc_splay_tree_join(&space->is_tree, &move);
785: ipc_splay_tree_join(&space->is_tree, &ignore);
786: }
787:
788: /*
789: * Add entries in the new part which still aren't used
790: * to the free list. Add them in reverse order,
791: * and set the generation number to -1, so that
792: * early allocations produce "natural" names.
793: */
794:
795: free_index = table[0].ie_next;
796: for (i = size-1; i >= osize; --i) {
797: ipc_entry_t entry = &table[i];
798:
799: if (entry->ie_bits == 0) {
800: entry->ie_bits = IE_BITS_GEN_MASK;
801: entry->ie_next = free_index;
802: free_index = i;
803: }
804: }
805: table[0].ie_next = free_index;
806:
807: /*
808: * Now we need to free the old table.
809: * If the space dies or grows while unlocked,
810: * then we can quit here.
811: */
812:
813: is_write_unlock(space);
814: thread_wakeup((event_t) space);
815: it_entries_free(oits, otable);
816: is_write_lock(space);
817: if (!space->is_active || (space->is_table_next != nits))
818: return KERN_SUCCESS;
819:
820: /*
821: * We might have moved enough entries from
822: * the splay tree into the table that
823: * the table can be profitably grown again.
824: *
825: * Note that if size == nsize, then
826: * space->is_tree_small == 0.
827: */
828: } while ((space->is_tree_small > 0) &&
829: (((nsize - size) * sizeof(struct ipc_entry)) <
830: (space->is_tree_small * sizeof(struct ipc_tree_entry))));
831:
832: return KERN_SUCCESS;
833: }
834:
835:
836: #if MACH_KDB
837: #include <ddb/db_output.h>
1.1.1.2 root 838: #include <kern/task.h>
839:
1.1 root 840: #define printf kdbprintf
841:
842: ipc_entry_t db_ipc_object_by_name(
843: task_t task,
844: mach_port_t name);
845:
846:
847: ipc_entry_t
848: db_ipc_object_by_name(
849: task_t task,
850: mach_port_t name)
851: {
852: ipc_space_t space = task->itk_space;
853: ipc_entry_t entry;
854:
855:
856: entry = ipc_entry_lookup(space, name);
857: if(entry != IE_NULL) {
858: iprintf("(task 0x%x, name 0x%x) ==> object 0x%x",
859: entry->ie_object);
860: return (ipc_entry_t) entry->ie_object;
861: }
862: return entry;
863: }
864: #endif /* MACH_KDB */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.