ipc: replace the IPC table with a radix tree

Currently, the port names are mapped to an IPC object (e.g. a port)
using a table.  This, however, requires large chunks of continuous
memory, and leads to scalability problems as virtual kernel memory is
a scarce resource.  To avoid excessive overhead, non-contiguous port
names are spilled into a splay tree.

Replace the IPC table with a radix tree.  As the radix tree is able to
store non-contiguous names with reasonable overhead, we can drop the
splay tree as well.

* ipc/ipc_entry.c (ipc_entry_tree_collision): Remove function.
(ipc_entry_cache): New variable.
(ipc_entry_lookup): Replace with a radix tree lookup.
(ipc_entry_get): The free list handling is changed a little.  Adopt
accordingly.
(ipc_entry_free_name): New function.
(ipc_entry_alloc): Adopt accordingly.
(ipc_entry_alloc_name): Likewise.
(ipc_entry_dealloc): Likewise.
(ipc_entry_grow_table): Remove function.
* ipc/ipc_entry.h (struct ipc_entry): Update comment, add field for
name and free list, remove unused fields.
(ipc_entry_cache, ie_alloc, ie_free): New declarations.
(struct ipc_tree_entry): Remove.  Also remove any related declarations.
(ipc_entry_grow_table): Remove declaration.
* ipc/ipc_init.c (ipc_bootstrap): Adopt initialization.
* ipc/ipc_kmsg.c (ipc_kmsg_copyout_header): Use `ipc_entry_alloc'
instead of re-coding it.  Adopt free list handling.
(ipc_kmsg_copyout_object): Adopt free list handling, store the name.
* ipc/ipc_object.c (ipc_object_copyout): Likewise.
(ipc_object_copyout_multiname): Likewise.
* ipc/ipc_space.c (ipc_space_create): Initialize radix tree and free list.
Drop table and splay tree initialization.
(ipc_space_destroy): Free ipc entries and radix tree, remove table and
splay tree cleanup.
* ipc/ipc_space.h (struct ipc_space): Add radix tree, free list, and size.
Remove all fields related to the table and splay tree.
* ddb/db_print.c (db_port_iterate): Adopt iteration.
(db_lookup_port): Adopt lookup.
* include/mach_debug/ipc_info.h: Remove unused parts of the debug interface.
* include/mach_debug/mach_debug.defs: Likewise.
* include/mach_debug/mach_debug_types.defs: Likewise.
* ipc/mach_debug.c: Likewise.
* ipc/ipc_right.c (ipc_right_reverse): Adopt lookup, store name.
(ipc_right_check): Adopt removal.
(ipc_right_destroy): Likewise.
(ipc_right_dealloc): Likewise.
(ipc_right_delta): Likewise.
(ipc_right_copyin): Adopt insertion, adopt removal.
(ipc_right_copyin_two): Adopt removal.
(ipc_right_copyout): Adopt insertion, adopt removal.
(ipc_right_rename): Likewise, also update comment.
* ipc/mach_port.c (mach_port_names): Adopt iteration.
(mach_port_get_set_status): Likewise.
* ipc/port.h: Update comment.
* ipc/ipc_hash.c: Delete file.
* ipc/ipc_hash.h: Likewise.
* ipc/ipc_splay.c: Likewise.
* ipc/ipc_splay.h: Likewise.
* Makefrag.am (libkernel_a_SOURCES): Remove these files.

1 files changed, 0 insertions, 920 deletions

diff --git a/ipc/ipc_splay.c b/ipc/ipc_splay.c
deleted file mode 100644
index 062a69f..0000000
--- a/ipc/ipc_splay.c
+++ /dev/null
@@ -1,920 +0,0 @@
-/* 
- * Mach Operating System
- * Copyright (c) 1991,1990,1989 Carnegie Mellon University
- * All Rights Reserved.
- * 
- * Permission to use, copy, modify and distribute this software and its
- * documentation is hereby granted, provided that both the copyright
- * notice and this permission notice appear in all copies of the
- * software, derivative works or modified versions, and any portions
- * thereof, and that both notices appear in supporting documentation.
- * 
- * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
- * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
- * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
- * 
- * Carnegie Mellon requests users of this software to return to
- * 
- *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
- *  School of Computer Science
- *  Carnegie Mellon University
- *  Pittsburgh PA 15213-3890
- * 
- * any improvements or extensions that they make and grant Carnegie Mellon
- * the rights to redistribute these changes.
- */
-/*
- */
-/*
- *	File:	ipc/ipc_splay.c
- *	Author:	Rich Draves
- *	Date:	1989
- *
- *	Primitive splay tree operations.
- */
-
-#include <mach/port.h>
-#include <kern/assert.h>
-#include <kern/macros.h>
-#include <ipc/ipc_entry.h>
-#include <ipc/ipc_splay.h>
-
-/*
- *	Splay trees are self-adjusting binary search trees.
- *	They have the following attractive properties:
- *		1) Space efficient; only two pointers per entry.
- *		2) Robust performance; amortized O(log n) per operation.
- *		3) Recursion not needed.
- *	This makes them a good fall-back data structure for those
- *	entries that don't fit into the lookup table.
- *
- *	The paper by Sleator and Tarjan, JACM v. 32, no. 3, pp. 652-686,
- *	describes the splaying operation.  ipc_splay_prim_lookup
- *	and ipc_splay_prim_assemble implement the top-down splay
- *	described on p. 669.
- *
- *	The tree is stored in an unassembled form.  If ist_root is null,
- *	then the tree has no entries.  Otherwise, ist_name records
- *	the value used for the last lookup.  ist_root points to the
- *	middle tree obtained from the top-down splay.  ist_ltree and
- *	ist_rtree point to left and right subtrees, whose entries
- *	are all smaller (larger) than those in the middle tree.
- *	ist_ltreep and ist_rtreep are pointers to fields in the
- *	left and right subtrees.  ist_ltreep points to the rchild field
- *	of the largest entry in ltree, and ist_rtreep points to the
- *	lchild field of the smallest entry in rtree.  The pointed-to
- *	fields aren't initialized.  If the left (right) subtree is null,
- *	then ist_ltreep (ist_rtreep) points to the ist_ltree (ist_rtree)
- *	field in the splay structure itself.
- *
- *	The primary advantage of the unassembled form is that repeated
- *	unsuccessful lookups are efficient.  In particular, an unsuccessful
- *	lookup followed by an insert only requires one splaying operation.
- *
- *	The traversal algorithm works via pointer inversion.
- *	When descending down the tree, child pointers are reversed
- *	to point back to the parent entry.  When ascending,
- *	the pointers are restored to their original value.
- *
- *	The biggest potential problem with the splay tree implementation
- *	is that the operations, even lookup, require an exclusive lock.
- *	If IPC spaces are protected with exclusive locks, then
- *	the splay tree doesn't require its own lock, and ist_lock/ist_unlock
- *	needn't do anything.  If IPC spaces are protected with read/write
- *	locks then ist_lock/ist_unlock should provide exclusive access.
- *
- *	If it becomes important to let lookups run in parallel,
- *	or if the restructuring makes lookups too expensive, then
- *	there is hope.  Use a read/write lock on the splay tree.
- *	Keep track of the number of entries in the tree.  When doing
- *	a lookup, first try a non-restructuring lookup with a read lock held,
- *	with a bound (based on log of size of the tree) on the number of
- *	entries to traverse.  If the lookup runs up against the bound,
- *	then take a write lock and do a reorganizing lookup.
- *	This way, if lookups only access roughly balanced parts
- *	of the tree, then lookups run in parallel and do no restructuring.
- *
- *	The traversal algorithm currently requires an exclusive lock.
- *	If that is a problem, the tree could be changed from an lchild/rchild
- *	representation to a leftmost child/right sibling representation.
- *	In conjunction with non-restructing lookups, this would let
- *	lookups and traversals all run in parallel.  But this representation
- *	is more complicated and would slow down the operations.
- */
-
-/*
- *	Boundary values to hand to ipc_splay_prim_lookup:
- */
-
-#define	MACH_PORT_SMALLEST	((mach_port_t) 0)
-#define MACH_PORT_LARGEST	((mach_port_t) ~0)
-
-/*
- *	Routine:	ipc_splay_prim_lookup
- *	Purpose:
- *		Searches for the node labeled name in the splay tree.
- *		Returns three nodes (treep, ltreep, rtreep) and
- *		two pointers to nodes (ltreepp, rtreepp).
- *
- *		ipc_splay_prim_lookup splits the supplied tree into
- *		three subtrees, left, middle, and right, returned
- *		in ltreep, treep, and rtreep.
- *
- *		If name is present in the tree, then it is at
- *		the root of the middle tree.  Otherwise, the root
- *		of the middle tree is the last node traversed.
- *
- *		ipc_splay_prim_lookup returns a pointer into
- *		the left subtree, to the rchild field of its
- *		largest node, in ltreepp.  It returns a pointer
- *		into the right subtree, to the lchild field of its
- *		smallest node, in rtreepp.
- */
-
-static void
-ipc_splay_prim_lookup(
-	mach_port_t		name,
-	ipc_tree_entry_t	tree,
-	ipc_tree_entry_t	*treep,
-	ipc_tree_entry_t	*ltreep,
-	ipc_tree_entry_t	**ltreepp,
-	ipc_tree_entry_t	*rtreep,
-	ipc_tree_entry_t	**rtreepp)
-{
-	mach_port_t tname;			/* temp name */
-	ipc_tree_entry_t lchild, rchild;	/* temp child pointers */
-
-	assert(tree != ITE_NULL);
-
-#define	link_left					\
-MACRO_BEGIN						\
-	*ltreep = tree;					\
-	ltreep = &tree->ite_rchild;			\
-	tree = *ltreep;					\
-MACRO_END
-
-#define	link_right					\
-MACRO_BEGIN						\
-	*rtreep = tree;					\
-	rtreep = &tree->ite_lchild;			\
-	tree = *rtreep;					\
-MACRO_END
-
-#define rotate_left					\
-MACRO_BEGIN						\
-	ipc_tree_entry_t temp = tree;			\
-							\
-	tree = temp->ite_rchild;			\
-	temp->ite_rchild = tree->ite_lchild;		\
-	tree->ite_lchild = temp;			\
-MACRO_END
-
-#define rotate_right					\
-MACRO_BEGIN						\
-	ipc_tree_entry_t temp = tree;			\
-							\
-	tree = temp->ite_lchild;			\
-	temp->ite_lchild = tree->ite_rchild;		\
-	tree->ite_rchild = temp;			\
-MACRO_END
-
-	while (name != (tname = tree->ite_name)) {
-		if (name < tname) {
-			/* descend to left */
-
-			lchild = tree->ite_lchild;
-			if (lchild == ITE_NULL)
-				break;
-			tname = lchild->ite_name;
-
-			if ((name < tname) &&
-			    (lchild->ite_lchild != ITE_NULL))
-				rotate_right;
-			link_right;
-			if ((name > tname) &&
-			    (lchild->ite_rchild != ITE_NULL))
-				link_left;
-		} else {
-			/* descend to right */
-
-			rchild = tree->ite_rchild;
-			if (rchild == ITE_NULL)
-				break;
-			tname = rchild->ite_name;
-
-			if ((name > tname) &&
-			    (rchild->ite_rchild != ITE_NULL))
-				rotate_left;
-			link_left;
-			if ((name < tname) &&
-			    (rchild->ite_lchild != ITE_NULL))
-				link_right;
-		}
-
-		assert(tree != ITE_NULL);
-	}
-
-	*treep = tree;
-	*ltreepp = ltreep;
-	*rtreepp = rtreep;
-
-#undef	link_left
-#undef	link_right
-#undef	rotate_left
-#undef	rotate_right
-}
-
-/*
- *	Routine:	ipc_splay_prim_assemble
- *	Purpose:
- *		Assembles the results of ipc_splay_prim_lookup
- *		into a splay tree with the found node at the root.
- *
- *		ltree and rtree are by-reference so storing
- *		through ltreep and rtreep can change them.
- */
-
-static void
-ipc_splay_prim_assemble(
-	ipc_tree_entry_t	tree,
-	ipc_tree_entry_t	*ltree,
-	ipc_tree_entry_t	*ltreep,
-	ipc_tree_entry_t	*rtree,
-	ipc_tree_entry_t	*rtreep)
-{
-	assert(tree != ITE_NULL);
-
-	*ltreep = tree->ite_lchild;
-	*rtreep = tree->ite_rchild;
-
-	tree->ite_lchild = *ltree;
-	tree->ite_rchild = *rtree;
-}
-
-/*
- *	Routine:	ipc_splay_tree_init
- *	Purpose:
- *		Initialize a raw splay tree for use.
- */
-
-void
-ipc_splay_tree_init(
-	ipc_splay_tree_t	splay)
-{
-	splay->ist_root = ITE_NULL;
-}
-
-/*
- *	Routine:	ipc_splay_tree_pick
- *	Purpose:
- *		Picks and returns a random entry in a splay tree.
- *		Returns FALSE if the splay tree is empty.
- */
-
-boolean_t
-ipc_splay_tree_pick(
-	ipc_splay_tree_t	splay,
-	mach_port_t		*namep,
-	ipc_tree_entry_t	*entryp)
-{
-	ipc_tree_entry_t root;
-
-	ist_lock(splay);
-
-	root = splay->ist_root;
-	if (root != ITE_NULL) {
-		*namep = root->ite_name;
-		*entryp = root;
-	}
-
-	ist_unlock(splay);
-
-	return root != ITE_NULL;
-}
-
-/*
- *	Routine:	ipc_splay_tree_lookup
- *	Purpose:
- *		Finds an entry in a splay tree.
- *		Returns ITE_NULL if not found.
- */
-
-ipc_tree_entry_t
-ipc_splay_tree_lookup(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name)
-{
-	ipc_tree_entry_t root;
-
-	ist_lock(splay);
-
-	root = splay->ist_root;
-	if (root != ITE_NULL) {
-		if (splay->ist_name != name) {
-			ipc_splay_prim_assemble(root,
-				&splay->ist_ltree, splay->ist_ltreep,
-				&splay->ist_rtree, splay->ist_rtreep);
-			ipc_splay_prim_lookup(name, root, &root,
-				&splay->ist_ltree, &splay->ist_ltreep,
-				&splay->ist_rtree, &splay->ist_rtreep);
-			splay->ist_name = name;
-			splay->ist_root = root;
-		}
-
-		if (name != root->ite_name)
-			root = ITE_NULL;
-	}
-
-	ist_unlock(splay);
-
-	return root;
-}
-
-/*
- *	Routine:	ipc_splay_tree_insert
- *	Purpose:
- *		Inserts a new entry into a splay tree.
- *		The caller supplies a new entry.
- *		The name can't already be present in the tree.
- */
-
-void
-ipc_splay_tree_insert(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry)
-{
-	ipc_tree_entry_t root;
-
-	assert(entry != ITE_NULL);
-
-	ist_lock(splay);
-
-	root = splay->ist_root;
-	if (root == ITE_NULL) {
-		entry->ite_lchild = ITE_NULL;
-		entry->ite_rchild = ITE_NULL;
-	} else {
-		if (splay->ist_name != name) {
-			ipc_splay_prim_assemble(root,
-				&splay->ist_ltree, splay->ist_ltreep,
-				&splay->ist_rtree, splay->ist_rtreep);
-			ipc_splay_prim_lookup(name, root, &root,
-				&splay->ist_ltree, &splay->ist_ltreep,
-				&splay->ist_rtree, &splay->ist_rtreep);
-		}
-
-		assert(root->ite_name != name);
-
-		if (name < root->ite_name) {
-			assert(root->ite_lchild == ITE_NULL);
-
-			*splay->ist_ltreep = ITE_NULL;
-			*splay->ist_rtreep = root;
-		} else {
-			assert(root->ite_rchild == ITE_NULL);
-
-			*splay->ist_ltreep = root;
-			*splay->ist_rtreep = ITE_NULL;
-		}
-
-		entry->ite_lchild = splay->ist_ltree;
-		entry->ite_rchild = splay->ist_rtree;
-	}
-
-	entry->ite_name = name;
-	splay->ist_root = entry;
-	splay->ist_name = name;
-	splay->ist_ltreep = &splay->ist_ltree;
-	splay->ist_rtreep = &splay->ist_rtree;
-
-	ist_unlock(splay);
-}
-
-/*
- *	Routine:	ipc_splay_tree_delete
- *	Purpose:
- *		Deletes an entry from a splay tree.
- *		The name must be present in the tree.
- *		Frees the entry.
- *
- *		The "entry" argument isn't currently used.
- *		Other implementations might want it, though.
- */
-
-void
-ipc_splay_tree_delete(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry)
-{
-	ipc_tree_entry_t root, saved;
-
-	ist_lock(splay);
-
-	root = splay->ist_root;
-	assert(root != ITE_NULL);
-
-	if (splay->ist_name != name) {
-		ipc_splay_prim_assemble(root,
-			&splay->ist_ltree, splay->ist_ltreep,
-			&splay->ist_rtree, splay->ist_rtreep);
-		ipc_splay_prim_lookup(name, root, &root,
-			&splay->ist_ltree, &splay->ist_ltreep,
-			&splay->ist_rtree, &splay->ist_rtreep);
-	}
-
-	assert(root->ite_name == name);
-	assert(root == entry);
-
-	*splay->ist_ltreep = root->ite_lchild;
-	*splay->ist_rtreep = root->ite_rchild;
-	ite_free(root);
-
-	root = splay->ist_ltree;
-	saved = splay->ist_rtree;
-
-	if (root == ITE_NULL)
-		root = saved;
-	else if (saved != ITE_NULL) {
-		/*
-		 *	Find the largest node in the left subtree, and splay it
-		 *	to the root.  Then add the saved right subtree.
-		 */
-
-		ipc_splay_prim_lookup(MACH_PORT_LARGEST, root, &root,
-			&splay->ist_ltree, &splay->ist_ltreep,
-			&splay->ist_rtree, &splay->ist_rtreep);
-		ipc_splay_prim_assemble(root,
-			&splay->ist_ltree, splay->ist_ltreep,
-			&splay->ist_rtree, splay->ist_rtreep);
-
-		assert(root->ite_rchild == ITE_NULL);
-		root->ite_rchild = saved;
-	}
-
-	splay->ist_root = root;
-	if (root != ITE_NULL) {
-		splay->ist_name = root->ite_name;
-		splay->ist_ltreep = &splay->ist_ltree;
-		splay->ist_rtreep = &splay->ist_rtree;
-	}
-
-	ist_unlock(splay);
-}
-
-/*
- *	Routine:	ipc_splay_tree_split
- *	Purpose:
- *		Split a splay tree.  Puts all entries smaller than "name"
- *		into a new tree, "small".
- *
- *		Doesn't do locking on "small", because nobody else
- *		should be fiddling with the uninitialized tree.
- */
-
-void
-ipc_splay_tree_split(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_splay_tree_t	small)
-{
-	ipc_tree_entry_t root;
-
-	ipc_splay_tree_init(small);
-
-	ist_lock(splay);
-
-	root = splay->ist_root;
-	if (root != ITE_NULL) {
-		/* lookup name, to get it (or last traversed) to the top */
-
-		if (splay->ist_name != name) {
-			ipc_splay_prim_assemble(root,
-				&splay->ist_ltree, splay->ist_ltreep,
-				&splay->ist_rtree, splay->ist_rtreep);
-			ipc_splay_prim_lookup(name, root, &root,
-				&splay->ist_ltree, &splay->ist_ltreep,
-				&splay->ist_rtree, &splay->ist_rtreep);
-		}
-
-		if (root->ite_name < name) {
-			/* root goes into small */
-
-			*splay->ist_ltreep = root->ite_lchild;
-			*splay->ist_rtreep = ITE_NULL;
-			root->ite_lchild = splay->ist_ltree;
-			assert(root->ite_rchild == ITE_NULL);
-
-			small->ist_root = root;
-			small->ist_name = root->ite_name;
-			small->ist_ltreep = &small->ist_ltree;
-			small->ist_rtreep = &small->ist_rtree;
-
-			/* rtree goes into splay */
-
-			root = splay->ist_rtree;
-			splay->ist_root = root;
-			if (root != ITE_NULL) {
-				splay->ist_name = root->ite_name;
-				splay->ist_ltreep = &splay->ist_ltree;
-				splay->ist_rtreep = &splay->ist_rtree;
-			}
-		} else {
-			/* root stays in splay */
-
-			*splay->ist_ltreep = root->ite_lchild;
-			root->ite_lchild = ITE_NULL;
-
-			splay->ist_root = root;
-			splay->ist_name = name;
-			splay->ist_ltreep = &splay->ist_ltree;
-
-			/* ltree goes into small */
-
-			root = splay->ist_ltree;
-			small->ist_root = root;
-			if (root != ITE_NULL) {
-				small->ist_name = root->ite_name;
-				small->ist_ltreep = &small->ist_ltree;
-				small->ist_rtreep = &small->ist_rtree;
-			}
-		}		
-	}
-
-	ist_unlock(splay);
-}
-
-/*
- *	Routine:	ipc_splay_tree_join
- *	Purpose:
- *		Joins two splay trees.  Merges the entries in "small",
- *		which must all be smaller than the entries in "splay",
- *		into "splay".
- */
-
-void
-ipc_splay_tree_join(
-	ipc_splay_tree_t	splay,
-	ipc_splay_tree_t	small)
-{
-	ipc_tree_entry_t sroot;
-
-	/* pull entries out of small */
-
-	ist_lock(small);
-
-	sroot = small->ist_root;
-	if (sroot != ITE_NULL) {
-		ipc_splay_prim_assemble(sroot,
-			&small->ist_ltree, small->ist_ltreep,
-			&small->ist_rtree, small->ist_rtreep);
-		small->ist_root = ITE_NULL;
-	}
-
-	ist_unlock(small);
-
-	/* put entries, if any, into splay */
-
-	if (sroot != ITE_NULL) {
-		ipc_tree_entry_t root;
-
-		ist_lock(splay);
-
-		root = splay->ist_root;
-		if (root == ITE_NULL) {
-			root = sroot;
-		} else {
-			/* get smallest entry in splay tree to top */
-
-			if (splay->ist_name != MACH_PORT_SMALLEST) {
-				ipc_splay_prim_assemble(root,
-					&splay->ist_ltree, splay->ist_ltreep,
-					&splay->ist_rtree, splay->ist_rtreep);
-				ipc_splay_prim_lookup(MACH_PORT_SMALLEST,
-					root, &root,
-					&splay->ist_ltree, &splay->ist_ltreep,
-					&splay->ist_rtree, &splay->ist_rtreep);
-			}
-
-			ipc_splay_prim_assemble(root,
-				&splay->ist_ltree, splay->ist_ltreep,
-				&splay->ist_rtree, splay->ist_rtreep);
-
-			assert(root->ite_lchild == ITE_NULL);
-			assert(sroot->ite_name < root->ite_name);
-			root->ite_lchild = sroot;
-		}
-
-		splay->ist_root = root;
-		splay->ist_name = root->ite_name;
-		splay->ist_ltreep = &splay->ist_ltree;
-		splay->ist_rtreep = &splay->ist_rtree;
-
-		ist_unlock(splay);
-	}
-}
-
-/*
- *	Routine:	ipc_splay_tree_bounds
- *	Purpose:
- *		Given a name, returns the largest value present
- *		in the tree that is smaller than or equal to the name,
- *		or ~0 if no such value exists.  Similarly, returns
- *		the smallest value present that is greater than or
- *		equal to the name, or 0 if no such value exists.
- *
- *		Hence, if
- *		lower = upper, then lower = name = upper
- *				and name is present in the tree
- *		lower = ~0 and upper = 0,
- *				then the tree is empty
- *		lower = ~0 and upper > 0, then name < upper
- *				and upper is smallest value in tree
- *		lower < ~0 and upper = 0, then lower < name
- *				and lower is largest value in tree
- *		lower < ~0 and upper > 0, then lower < name < upper
- *				and they are tight bounds on name
- *
- *		(Note MACH_PORT_SMALLEST = 0 and MACH_PORT_LARGEST = ~0.)
- */
-
-void
-ipc_splay_tree_bounds(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	mach_port_t		*lowerp, 
-	mach_port_t		*upperp)
-{
-	ipc_tree_entry_t root;
-
-	ist_lock(splay);
-
-	root = splay->ist_root;
-	if (root == ITE_NULL) {
-		*lowerp = MACH_PORT_LARGEST;
-		*upperp = MACH_PORT_SMALLEST;
-	} else {
-		mach_port_t rname;
-
-		if (splay->ist_name != name) {
-			ipc_splay_prim_assemble(root,
-				&splay->ist_ltree, splay->ist_ltreep,
-				&splay->ist_rtree, splay->ist_rtreep);
-			ipc_splay_prim_lookup(name, root, &root,
-				&splay->ist_ltree, &splay->ist_ltreep,
-				&splay->ist_rtree, &splay->ist_rtreep);
-			splay->ist_name = name;
-			splay->ist_root = root;
-		}
-
-		rname = root->ite_name;
-
-		/*
-		 *	OK, it's a hack.  We convert the ltreep and rtreep
-		 *	pointers back into real entry pointers,
-		 *	so we can pick the names out of the entries.
-		 */
-
-		if (rname <= name)
-			*lowerp = rname;
-		else if (splay->ist_ltreep == &splay->ist_ltree)
-			*lowerp = MACH_PORT_LARGEST;
-		else {
-			ipc_tree_entry_t entry;
-
-			entry = (ipc_tree_entry_t)
-				((char *)splay->ist_ltreep -
-				 ((char *)&root->ite_rchild -
-				  (char *)root));
-			*lowerp = entry->ite_name;
-		}
-
-		if (rname >= name)
-			*upperp = rname;
-		else if (splay->ist_rtreep == &splay->ist_rtree)
-			*upperp = MACH_PORT_SMALLEST;
-		else {
-			ipc_tree_entry_t entry;
-
-			entry = (ipc_tree_entry_t)
-				((char *)splay->ist_rtreep -
-				 ((char *)&root->ite_lchild -
-				  (char *)root));
-			*upperp = entry->ite_name;
-		}
-	}
-
-	ist_unlock(splay);
-}
-
-/*
- *	Routine:	ipc_splay_traverse_start
- *	Routine:	ipc_splay_traverse_next
- *	Routine:	ipc_splay_traverse_finish
- *	Purpose:
- *		Perform a symmetric order traversal of a splay tree.
- *	Usage:
- *		for (entry = ipc_splay_traverse_start(splay);
- *		     entry != ITE_NULL;
- *		     entry = ipc_splay_traverse_next(splay, delete)) {
- *			do something with entry
- *		}
- *		ipc_splay_traverse_finish(splay);
- *
- *		If "delete" is TRUE, then the current entry
- *		is removed from the tree and deallocated.
- *
- *		During the traversal, the splay tree is locked.
- */
-
-ipc_tree_entry_t
-ipc_splay_traverse_start(
-	ipc_splay_tree_t	splay)
-{
-	ipc_tree_entry_t current, parent;
-
-	ist_lock(splay);
-
-	current = splay->ist_root;
-	if (current != ITE_NULL) {
-		ipc_splay_prim_assemble(current,
-			&splay->ist_ltree, splay->ist_ltreep,
-			&splay->ist_rtree, splay->ist_rtreep);
-
-		parent = ITE_NULL;
-
-		while (current->ite_lchild != ITE_NULL) {
-			ipc_tree_entry_t next;
-
-			next = current->ite_lchild;
-			current->ite_lchild = parent;
-			parent = current;
-			current = next;
-		}
-
-		splay->ist_ltree = current;
-		splay->ist_rtree = parent;
-	}
-
-	return current;
-}
-
-ipc_tree_entry_t
-ipc_splay_traverse_next(
-	ipc_splay_tree_t	splay,
-	boolean_t		delete)
-{
-	ipc_tree_entry_t current, parent;
-
-	/* pick up where traverse_entry left off */
-
-	current = splay->ist_ltree;
-	parent = splay->ist_rtree;
-	assert(current != ITE_NULL);
-
-	if (!delete)
-		goto traverse_right;
-
-	/* we must delete current and patch the tree */
-
-	if (current->ite_lchild == ITE_NULL) {
-		if (current->ite_rchild == ITE_NULL) {
-			/* like traverse_back, but with deletion */
-
-			if (parent == ITE_NULL) {
-				ite_free(current);
-
-				splay->ist_root = ITE_NULL;
-				return ITE_NULL;
-			}
-
-			if (current->ite_name < parent->ite_name) {
-				ite_free(current);
-
-				current = parent;
-				parent = current->ite_lchild;
-				current->ite_lchild = ITE_NULL;
-				goto traverse_entry;
-			} else {
-				ite_free(current);
-
-				current = parent;
-				parent = current->ite_rchild;
-				current->ite_rchild = ITE_NULL;
-				goto traverse_back;
-			}
-		} else {
-			ipc_tree_entry_t prev;
-
-			prev = current;
-			current = current->ite_rchild;
-			ite_free(prev);
-			goto traverse_left;
-		}
-	} else {
-		if (current->ite_rchild == ITE_NULL) {
-			ipc_tree_entry_t prev;
-
-			prev = current;
-			current = current->ite_lchild;
-			ite_free(prev);
-			goto traverse_back;
-		} else {
-			ipc_tree_entry_t prev;
-			ipc_tree_entry_t ltree, rtree;
-			ipc_tree_entry_t *ltreep, *rtreep;
-
-			/* replace current with largest of left children */
-
-			prev = current;
-			ipc_splay_prim_lookup(MACH_PORT_LARGEST,
-				current->ite_lchild, &current,
-				&ltree, &ltreep, &rtree, &rtreep);
-			ipc_splay_prim_assemble(current,
-				&ltree, ltreep, &rtree, rtreep);
-
-			assert(current->ite_rchild == ITE_NULL);
-			current->ite_rchild = prev->ite_rchild;
-			ite_free(prev);
-			goto traverse_right;
-		}
-	}
-	/*NOTREACHED*/
-
-	/*
-	 *	A state machine:  for each entry, we
-	 *		1) traverse left subtree
-	 *		2) traverse the entry
-	 *		3) traverse right subtree
-	 *		4) traverse back to parent
-	 */
-
-    traverse_left:
-	if (current->ite_lchild != ITE_NULL) {
-		ipc_tree_entry_t next;
-
-		next = current->ite_lchild;
-		current->ite_lchild = parent;
-		parent = current;
-		current = next;
-		goto traverse_left;
-	}
-
-    traverse_entry:
-	splay->ist_ltree = current;
-	splay->ist_rtree = parent;
-	return current;
-
-    traverse_right:
-	if (current->ite_rchild != ITE_NULL) {
-		ipc_tree_entry_t next;
-
-		next = current->ite_rchild;
-		current->ite_rchild = parent;
-		parent = current;
-		current = next;
-		goto traverse_left;
-	}
-
-    traverse_back:
-	if (parent == ITE_NULL) {
-		splay->ist_root = current;
-		return ITE_NULL;
-	}
-
-	if (current->ite_name < parent->ite_name) {
-		ipc_tree_entry_t prev;
-
-		prev = current;
-		current = parent;
-		parent = current->ite_lchild;
-		current->ite_lchild = prev;
-		goto traverse_entry;
-	} else {
-		ipc_tree_entry_t prev;
-
-		prev = current;
-		current = parent;
-		parent = current->ite_rchild;
-		current->ite_rchild = prev;
-		goto traverse_back;
-	}
-}
-
-void
-ipc_splay_traverse_finish(
-	ipc_splay_tree_t	splay)
-{
-	ipc_tree_entry_t root;
-
-	root = splay->ist_root;
-	if (root != ITE_NULL) {
-		splay->ist_name = root->ite_name;
-		splay->ist_ltreep = &splay->ist_ltree;
-		splay->ist_rtreep = &splay->ist_rtree;
-	}
-
-	ist_unlock(splay);
-}
-