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