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.

15 files changed, 189 insertions, 2814 deletions

diff --git a/ipc/ipc_entry.c b/ipc/ipc_entry.c
index 5b9fd98..2d6e665 100644
--- a/ipc/ipc_entry.c
+++ b/ipc/ipc_entry.c
@@ -46,45 +46,10 @@
 #include <ipc/ipc_types.h>
 #include <ipc/ipc_entry.h>
 #include <ipc/ipc_space.h>
-#include <ipc/ipc_splay.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_table.h>
 #include <ipc/ipc_object.h>
 
-struct kmem_cache ipc_tree_entry_cache;
-
-/*
- *	Routine:	ipc_entry_tree_collision
- *	Purpose:
- *		Checks if "name" collides with an allocated name
- *		in the space's tree.  That is, returns TRUE
- *		if the splay tree contains a name with the same
- *		index as "name".
- *	Conditions:
- *		The space is locked (read or write) and active.
- */
-
-boolean_t
-ipc_entry_tree_collision(
-	ipc_space_t	space,
-	mach_port_t	name)
-{
-	mach_port_index_t index;
-	mach_port_t lower, upper;
-
-	assert(space->is_active);
-
-	/*
-	 *	Check if we collide with the next smaller name
-	 *	or the next larger name.
-	 */
-
-	ipc_splay_tree_bounds(&space->is_tree, name, &lower, &upper);
-
-	index = MACH_PORT_INDEX(name);
-	return (((lower != ~0) && (MACH_PORT_INDEX(lower) == index)) ||
-		((upper != 0) && (MACH_PORT_INDEX(upper) == index)));
-}
+struct kmem_cache ipc_entry_cache;
 
 /*
  *	Routine:	ipc_entry_lookup
@@ -100,29 +65,13 @@ ipc_entry_lookup(
 	ipc_space_t space,
 	mach_port_t name)
 {
-	mach_port_index_t index;
 	ipc_entry_t entry;
 
 	assert(space->is_active);
-
-	index = MACH_PORT_INDEX(name);
-	if (index < space->is_table_size) {
-		entry = &space->is_table[index];
-		if (IE_BITS_GEN(entry->ie_bits) != MACH_PORT_GEN(name))
-			if (entry->ie_bits & IE_BITS_COLLISION) {
-				assert(space->is_tree_total > 0);
-				goto tree_lookup;
-			} else
-				entry = IE_NULL;
-		else if (IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_NONE)
-			entry = IE_NULL;
-	} else if (space->is_tree_total == 0)
-		entry = IE_NULL;
-	else
-	    tree_lookup:
-		entry = (ipc_entry_t)
-				ipc_splay_tree_lookup(&space->is_tree, name);
-
+	entry = rdxtree_lookup(&space->is_map, (rdxtree_key_t) name);
+	if (entry != IE_NULL
+	    && IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_NONE)
+		entry = NULL;
 	assert((entry == IE_NULL) || IE_BITS_TYPE(entry->ie_bits));
 	return entry;
 }
@@ -145,21 +94,18 @@ ipc_entry_get(
 	mach_port_t *namep,
 	ipc_entry_t *entryp)
 {
-	ipc_entry_t table;
-	mach_port_index_t first_free;
 	mach_port_t new_name;
 	ipc_entry_t free_entry;
 
 	assert(space->is_active);
 
-	table = space->is_table;
-	first_free = table->ie_next;
-
-	if (first_free == 0)
+	/* Get entry from the free list.  */
+	free_entry = space->is_free_list;
+	if (free_entry == IE_NULL)
 		return KERN_NO_SPACE;
 
-	free_entry = &table[first_free];
-	table->ie_next = free_entry->ie_next;
+	space->is_free_list = free_entry->ie_next_free;
+	space->is_free_list_size -= 1;
 
 	/*
 	 *	Initialize the new entry.  We need only
@@ -173,7 +119,7 @@ ipc_entry_get(
 	gen = free_entry->ie_bits + IE_BITS_GEN_ONE;
 	free_entry->ie_bits = gen;
 	free_entry->ie_request = 0;
-	new_name = MACH_PORT_MAKE(first_free, gen);
+	new_name = MACH_PORT_MAKE(free_entry->ie_name, gen);
     }
 
 	/*
@@ -186,6 +132,7 @@ ipc_entry_get(
 	assert(MACH_PORT_VALID(new_name));
 	assert(free_entry->ie_object == IO_NULL);
 
+	space->is_size += 1;
 	*namep = new_name;
 	*entryp = free_entry;
 	return KERN_SUCCESS;
@@ -212,23 +159,44 @@ ipc_entry_alloc(
 	ipc_entry_t	*entryp)
 {
 	kern_return_t kr;
+	ipc_entry_t entry;
+	rdxtree_key_t key;
 
 	is_write_lock(space);
 
-	for (;;) {
-		if (!space->is_active) {
-			is_write_unlock(space);
-			return KERN_INVALID_TASK;
-		}
+	if (!space->is_active) {
+		is_write_unlock(space);
+		return KERN_INVALID_TASK;
+	}
 
-		kr = ipc_entry_get(space, namep, entryp);
-		if (kr == KERN_SUCCESS)
-			return kr;
+	kr = ipc_entry_get(space, namep, entryp);
+	if (kr == KERN_SUCCESS)
+		/* Success.  Space is write-locked.  */
+		return kr;
 
-		kr = ipc_entry_grow_table(space);
-		if (kr != KERN_SUCCESS)
-			return kr; /* space is unlocked */
+	entry = ie_alloc();
+	if (entry == IE_NULL) {
+		is_write_unlock(space);
+		return KERN_RESOURCE_SHORTAGE;
+	}
+
+	kr = rdxtree_insert_alloc(&space->is_map, entry, &key);
+	if (kr) {
+		is_write_unlock(space);
+		ie_free(entry);
+		return kr;
 	}
+	space->is_size += 1;
+
+	entry->ie_bits = 0;
+	entry->ie_object = IO_NULL;
+	entry->ie_request = 0;
+	entry->ie_name = (mach_port_t) key;
+
+	*entryp = entry;
+	*namep = (mach_port_t) key;
+	/* Success.  Space is write-locked.  */
+	return KERN_SUCCESS;
 }
 
 /*
@@ -252,166 +220,77 @@ ipc_entry_alloc_name(
 	mach_port_t	name,
 	ipc_entry_t	*entryp)
 {
-	mach_port_index_t index = MACH_PORT_INDEX(name);
-	mach_port_gen_t gen = MACH_PORT_GEN(name);
-	ipc_tree_entry_t tree_entry = ITE_NULL;
-
+	kern_return_t kr;
+	ipc_entry_t entry, e, *prevp;
+	void **slot;
 	assert(MACH_PORT_VALID(name));
 
-
 	is_write_lock(space);
 
-	for (;;) {
-		ipc_entry_t entry;
-		ipc_tree_entry_t tentry;
-		ipc_table_size_t its;
+	if (!space->is_active) {
+		is_write_unlock(space);
+		return KERN_INVALID_TASK;
+	}
+
+	slot = rdxtree_lookup_slot(&space->is_map, (rdxtree_key_t) name);
+	if (slot != NULL)
+		entry = *(ipc_entry_t *) slot;
 
-		if (!space->is_active) {
+	if (slot == NULL || entry == IE_NULL) {
+		entry = ie_alloc();
+		if (entry == IE_NULL) {
 			is_write_unlock(space);
-			if (tree_entry) ite_free(tree_entry);
-			return KERN_INVALID_TASK;
-		}
-
-		/*
-		 *	If we are under the table cutoff,
-		 *	there are three cases:
-		 *		1) The entry is inuse, for the same name
-		 *		2) The entry is inuse, for a different name
-		 *		3) The entry is free
-		 */
-
-		if ((0 < index) && (index < space->is_table_size)) {
-			ipc_entry_t table = space->is_table;
-
-			entry = &table[index];
-
-			if (IE_BITS_TYPE(entry->ie_bits)) {
-				if (IE_BITS_GEN(entry->ie_bits) == gen) {
-					*entryp = entry;
-					if (tree_entry) ite_free(tree_entry);
-					return KERN_SUCCESS;
-				}
-			} else {
-				mach_port_index_t free_index, next_index;
-
-				/*
-				 *	Rip the entry out of the free list.
-				 */
-
-				for (free_index = 0;
-				     (next_index = table[free_index].ie_next)
-							!= index;
-				     free_index = next_index)
-					continue;
-
-				table[free_index].ie_next =
-					table[next_index].ie_next;
-
-				entry->ie_bits = gen;
-				assert(entry->ie_object == IO_NULL);
-				entry->ie_request = 0;
-
-				*entryp = entry;
-				if (tree_entry) ite_free(tree_entry);
-				return KERN_SUCCESS;
-			}
+			return KERN_RESOURCE_SHORTAGE;
 		}
 
-		/*
-		 *	Before trying to allocate any memory,
-		 *	check if the entry already exists in the tree.
-		 *	This avoids spurious resource errors.
-		 *	The splay tree makes a subsequent lookup/insert
-		 *	of the same name cheap, so this costs little.
-		 */
-
-		if ((space->is_tree_total > 0) &&
-		    ((tentry = ipc_splay_tree_lookup(&space->is_tree, name))
-							!= ITE_NULL)) {
-			assert(tentry->ite_space == space);
-			assert(IE_BITS_TYPE(tentry->ite_bits));
-
-			*entryp = &tentry->ite_entry;
-			if (tree_entry) ite_free(tree_entry);
-			return KERN_SUCCESS;
-		}
+		entry->ie_bits = 0;
+		entry->ie_object = IO_NULL;
+		entry->ie_request = 0;
+		entry->ie_name = name;
 
-		its = space->is_table_next;
-
-		/*
-		 *	Check if the table should be grown.
-		 *
-		 *	Note that if space->is_table_size == its->its_size,
-		 *	then we won't ever try to grow the table.
-		 *
-		 *	Note that we are optimistically assuming that name
-		 *	doesn't collide with any existing names.  (So if
-		 *	it were entered into the tree, is_tree_small would
-		 *	be incremented.)  This is OK, because even in that
-		 *	case, we don't lose memory by growing the table.
-		 */
-
-		if ((space->is_table_size <= index) &&
-		    (index < its->its_size) &&
-		    (((its->its_size - space->is_table_size) *
-		      sizeof(struct ipc_entry)) <
-		     ((space->is_tree_small + 1) *
-		      sizeof(struct ipc_tree_entry)))) {
-			kern_return_t kr;
-
-			/*
-			 *	Can save space by growing the table.
-			 *	Because the space will be unlocked,
-			 *	we must restart.
-			 */
-
-			kr = ipc_entry_grow_table(space);
-			assert(kr != KERN_NO_SPACE);
+		if (slot != NULL)
+			rdxtree_replace_slot(slot, entry);
+		else {
+			kr = rdxtree_insert(&space->is_map,
+					    (rdxtree_key_t) name, entry);
 			if (kr != KERN_SUCCESS) {
-				/* space is unlocked */
-				if (tree_entry) ite_free(tree_entry);
+				is_write_unlock(space);
+				ie_free(entry);
 				return kr;
 			}
-
-			continue;
-		}
-
-		/*
-		 *	If a splay-tree entry was allocated previously,
-		 *	go ahead and insert it into the tree.
-		 */
-
-		if (tree_entry != ITE_NULL) {
-			space->is_tree_total++;
-
-			if (index < space->is_table_size)
-				space->is_table[index].ie_bits |=
-					IE_BITS_COLLISION;
-			else if ((index < its->its_size) &&
-				 !ipc_entry_tree_collision(space, name))
-				space->is_tree_small++;
-
-			ipc_splay_tree_insert(&space->is_tree,
-					      name, tree_entry);
-
-			tree_entry->ite_bits = 0;
-			tree_entry->ite_object = IO_NULL;
-			tree_entry->ite_request = 0;
-			tree_entry->ite_space = space;
-			*entryp = &tree_entry->ite_entry;
-			return KERN_SUCCESS;
 		}
+		space->is_size += 1;
 
-		/*
-		 *	Allocate a tree entry and try again.
-		 */
+		*entryp = entry;
+		/* Success.  Space is write-locked.  */
+		return KERN_SUCCESS;
+	}
 
-		is_write_unlock(space);
-		tree_entry = ite_alloc();
-		if (tree_entry == ITE_NULL)
-			return KERN_RESOURCE_SHORTAGE;
-		is_write_lock(space);
+	if (IE_BITS_TYPE(entry->ie_bits)) {
+		/* Used entry.  */
+		*entryp = entry;
+		/* Success.  Space is write-locked.  */
+		return KERN_SUCCESS;
 	}
+
+	/* Free entry.  Rip the entry out of the free list.  */
+	for (prevp = &space->is_free_list, e = space->is_free_list;
+	     e != entry;
+	     ({ prevp = &e->ie_next_free; e = e->ie_next_free; }))
+		continue;
+
+	*prevp = entry->ie_next_free;
+	space->is_free_list_size -= 1;
+
+	entry->ie_bits = 0;
+	assert(entry->ie_object == IO_NULL);
+	assert(entry->ie_name == name);
+	entry->ie_request = 0;
+
+	space->is_size += 1;
+	*entryp = entry;
+	/* Success.  Space is write-locked.  */
+	return KERN_SUCCESS;
 }
 
 /*
@@ -429,405 +308,20 @@ ipc_entry_dealloc(
 	mach_port_t	name,
 	ipc_entry_t	entry)
 {
-	ipc_entry_t table;
-	ipc_entry_num_t size;
-	mach_port_index_t index;
-
 	assert(space->is_active);
 	assert(entry->ie_object == IO_NULL);
 	assert(entry->ie_request == 0);
 
-	index = MACH_PORT_INDEX(name);
-	table = space->is_table;
-	size = space->is_table_size;
-
-	if ((index < size) && (entry == &table[index])) {
-		assert(IE_BITS_GEN(entry->ie_bits) == MACH_PORT_GEN(name));
-
-		if (entry->ie_bits & IE_BITS_COLLISION) {
-			struct ipc_splay_tree small, collisions;
-			ipc_tree_entry_t tentry;
-			mach_port_t tname;
-			boolean_t pick;
-			ipc_entry_bits_t bits;
-			ipc_object_t obj;
-
-			/* must move an entry from tree to table */
-
-			ipc_splay_tree_split(&space->is_tree,
-					     MACH_PORT_MAKE(index+1, 0),
-					     &collisions);
-			ipc_splay_tree_split(&collisions,
-					     MACH_PORT_MAKE(index, 0),
-					     &small);
-
-			pick = ipc_splay_tree_pick(&collisions,
-						   &tname, &tentry);
-			assert(pick);
-			assert(MACH_PORT_INDEX(tname) == index);
-
-			bits = tentry->ite_bits;
-			entry->ie_bits = bits | MACH_PORT_GEN(tname);
-			entry->ie_object = obj = tentry->ite_object;
-			entry->ie_request = tentry->ite_request;
-			assert(tentry->ite_space == space);
-
-			if (IE_BITS_TYPE(bits) == MACH_PORT_TYPE_SEND) {
-				ipc_hash_global_delete(space, obj,
-						       tname, tentry);
-				ipc_hash_local_insert(space, obj,
-						      index, entry);
-			}
-
-			ipc_splay_tree_delete(&collisions, tname, tentry);
-
-			assert(space->is_tree_total > 0);
-			space->is_tree_total--;
-
-			/* check if collision bit should still be on */
-
-			pick = ipc_splay_tree_pick(&collisions,
-						   &tname, &tentry);
-			if (pick) {
-				entry->ie_bits |= IE_BITS_COLLISION;
-				ipc_splay_tree_join(&space->is_tree,
-						    &collisions);
-			}
-
-			ipc_splay_tree_join(&space->is_tree, &small);
-		} else {
-			entry->ie_bits &= IE_BITS_GEN_MASK;
-			entry->ie_next = table->ie_next;
-			table->ie_next = index;
-		}
+	if (space->is_free_list_size < IS_FREE_LIST_SIZE_LIMIT) {
+		space->is_free_list_size += 1;
+		entry->ie_bits &= IE_BITS_GEN_MASK;
+		entry->ie_next_free = space->is_free_list;
+		space->is_free_list = entry;
 	} else {
-		ipc_tree_entry_t tentry = (ipc_tree_entry_t) entry;
-
-		assert(tentry->ite_space == space);
-
-		ipc_splay_tree_delete(&space->is_tree, name, tentry);
-
-		assert(space->is_tree_total > 0);
-		space->is_tree_total--;
-
-		if (index < size) {
-			ipc_entry_t ientry = &table[index];
-
-			assert(ientry->ie_bits & IE_BITS_COLLISION);
-
-			if (!ipc_entry_tree_collision(space, name))
-				ientry->ie_bits &= ~IE_BITS_COLLISION;
-		} else if ((index < space->is_table_next->its_size) &&
-			   !ipc_entry_tree_collision(space, name)) {
-			assert(space->is_tree_small > 0);
-			space->is_tree_small--;
-		}
+		rdxtree_remove(&space->is_map, (rdxtree_key_t) name);
+		ie_free(entry);
 	}
-}
-
-/*
- *	Routine:	ipc_entry_grow_table
- *	Purpose:
- *		Grows the table in a space.
- *	Conditions:
- *		The space must be write-locked and active before.
- *		If successful, it is also returned locked.
- *		Allocates memory.
- *	Returns:
- *		KERN_SUCCESS		Grew the table.
- *		KERN_SUCCESS		Somebody else grew the table.
- *		KERN_SUCCESS		The space died.
- *		KERN_NO_SPACE		Table has maximum size already.
- *		KERN_RESOURCE_SHORTAGE	Couldn't allocate a new table.
- */
-
-kern_return_t
-ipc_entry_grow_table(ipc_space_t space)
-{
-	ipc_entry_num_t osize, size, nsize;
-
-	do {
-		ipc_entry_t otable, table;
-		ipc_table_size_t oits, its, nits;
-		mach_port_index_t i, free_index;
-
-		assert(space->is_active);
-
-		if (space->is_growing) {
-			/*
-			 *	Somebody else is growing the table.
-			 *	We just wait for them to finish.
-			 */
-
-			assert_wait((event_t) space, FALSE);
-			is_write_unlock(space);
-			thread_block((void (*)()) 0);
-			is_write_lock(space);
-			return KERN_SUCCESS;
-		}
-
-		otable = space->is_table;
-		its = space->is_table_next;
-		size = its->its_size;
-		oits = its - 1;
-		osize = oits->its_size;
-		nits = its + 1;
-		nsize = nits->its_size;
-
-		if (osize == size) {
-			is_write_unlock(space);
-			printf_once("no more room for ipc_entry_grow_table in space %p\n", space);
-			return KERN_NO_SPACE;
-		}
-
-		assert((osize < size) && (size <= nsize));
-
-		/*
-		 *	OK, we'll attempt to grow the table.
-		 *	The realloc requires that the old table
-		 *	remain in existence.
-		 */
-
-		space->is_growing = TRUE;
-		is_write_unlock(space);
-		if (it_entries_reallocable(oits))
-			table = it_entries_realloc(oits, otable, its);
-		else
-			table = it_entries_alloc(its);
-		is_write_lock(space);
-		space->is_growing = FALSE;
-
-		/*
-		 *	We need to do a wakeup on the space,
-		 *	to rouse waiting threads.  We defer
-		 *	this until the space is unlocked,
-		 *	because we don't want them to spin.
-		 */
-
-		if (table == IE_NULL) {
-			is_write_unlock(space);
-			thread_wakeup((event_t) space);
-			return KERN_RESOURCE_SHORTAGE;
-		}
-
-		if (!space->is_active) {
-			/*
-			 *	The space died while it was unlocked.
-			 */
-
-			is_write_unlock(space);
-			thread_wakeup((event_t) space);
-			it_entries_free(its, table);
-			ipc_reverse_remove_all(space);
-			is_write_lock(space);
-			return KERN_SUCCESS;
-		}
-
-		assert(space->is_table == otable);
-		assert(space->is_table_next == its);
-		assert(space->is_table_size == osize);
-
-		space->is_table = table;
-		space->is_table_size = size;
-		space->is_table_next = nits;
-
-		/*
-		 *	If we did a realloc, it remapped the data.
-		 *	Otherwise we copy by hand first.  Then we have
-		 *	to clear the index fields in the old part and
-		 *	zero the new part.
-		 */
-
-		if (!it_entries_reallocable(oits))
-			memcpy(table, otable,
-			      osize * sizeof(struct ipc_entry));
-
-		(void) memset((void *) (table + osize), 0,
-		      (size - osize) * sizeof(struct ipc_entry));
-
-		/*
-		 *	Put old entries into the reverse hash table.
-		 */
-
-		ipc_reverse_remove_all(space);
-		for (i = 0; i < osize; i++) {
-			ipc_entry_t entry = &table[i];
-
-			if (IE_BITS_TYPE(entry->ie_bits) ==
-						MACH_PORT_TYPE_SEND)
-				ipc_hash_local_insert(space, entry->ie_object,
-						      i, entry);
-		}
-
-		/*
-		 *	If there are entries in the splay tree,
-		 *	then we have work to do:
-		 *		1) transfer entries to the table
-		 *		2) update is_tree_small
-		 */
-
-		if (space->is_tree_total > 0) {
-			mach_port_index_t index;
-			boolean_t delete;
-			struct ipc_splay_tree ignore;
-			struct ipc_splay_tree move;
-			struct ipc_splay_tree small;
-			ipc_entry_num_t nosmall;
-			ipc_tree_entry_t tentry;
-
-			/*
-			 *	The splay tree divides into four regions,
-			 *	based on the index of the entries:
-			 *		1) 0 <= index < osize
-			 *		2) osize <= index < size
-			 *		3) size <= index < nsize
-			 *		4) nsize <= index
-			 *
-			 *	Entries in the first part are ignored.
-			 *	Entries in the second part, that don't
-			 *	collide, are moved into the table.
-			 *	Entries in the third part, that don't
-			 *	collide, are counted for is_tree_small.
-			 *	Entries in the fourth part are ignored.
-			 */
-
-			ipc_splay_tree_split(&space->is_tree,
-					     MACH_PORT_MAKE(nsize, 0),
-					     &small);
-			ipc_splay_tree_split(&small,
-					     MACH_PORT_MAKE(size, 0),
-					     &move);
-			ipc_splay_tree_split(&move,
-					     MACH_PORT_MAKE(osize, 0),
-					     &ignore);
-
-			/* move entries into the table */
-
-			for (tentry = ipc_splay_traverse_start(&move);
-			     tentry != ITE_NULL;
-			     tentry = ipc_splay_traverse_next(&move, delete)) {
-				mach_port_t name;
-				mach_port_gen_t gen;
-				mach_port_type_t type;
-				ipc_entry_bits_t bits;
-				ipc_object_t obj;
-				ipc_entry_t entry;
-
-				name = tentry->ite_name;
-				gen = MACH_PORT_GEN(name);
-				index = MACH_PORT_INDEX(name);
-
-				assert(tentry->ite_space == space);
-				assert((osize <= index) && (index < size));
-
-				entry = &table[index];
-
-				/* collision with previously moved entry? */
-
-				bits = entry->ie_bits;
-				if (bits != 0) {
-					assert(IE_BITS_TYPE(bits));
-					assert(IE_BITS_GEN(bits) != gen);
-
-					entry->ie_bits =
-						bits | IE_BITS_COLLISION;
-					delete = FALSE;
-					continue;
-				}
-
-				bits = tentry->ite_bits;
-				type = IE_BITS_TYPE(bits);
-				assert(type != MACH_PORT_TYPE_NONE);
-
-				entry->ie_bits = bits | gen;
-				entry->ie_object = obj = tentry->ite_object;
-				entry->ie_request = tentry->ite_request;
-
-				if (type == MACH_PORT_TYPE_SEND) {
-					ipc_hash_global_delete(space, obj,
-							       name, tentry);
-					ipc_hash_local_insert(space, obj,
-							      index, entry);
-				}
-
-				space->is_tree_total--;
-				delete = TRUE;
-			}
-			ipc_splay_traverse_finish(&move);
-
-			/* count entries for is_tree_small */
-
-			nosmall = 0; index = 0;
-			for (tentry = ipc_splay_traverse_start(&small);
-			     tentry != ITE_NULL;
-			     tentry = ipc_splay_traverse_next(&small, FALSE)) {
-				mach_port_index_t nindex;
-
-				nindex = MACH_PORT_INDEX(tentry->ite_name);
-
-				if (nindex != index) {
-					nosmall++;
-					index = nindex;
-				}
-			}
-			ipc_splay_traverse_finish(&small);
-
-			assert(nosmall <= (nsize - size));
-			assert(nosmall <= space->is_tree_total);
-			space->is_tree_small = nosmall;
-
-			/* put the splay tree back together */
-
-			ipc_splay_tree_join(&space->is_tree, &small);
-			ipc_splay_tree_join(&space->is_tree, &move);
-			ipc_splay_tree_join(&space->is_tree, &ignore);
-		}
-
-		/*
-		 *	Add entries in the new part which still aren't used
-		 *	to the free list.  Add them in reverse order,
-		 *	and set the generation number to -1, so that
-		 *	early allocations produce "natural" names.
-		 */
-
-		free_index = table[0].ie_next;
-		for (i = size-1; i >= osize; --i) {
-			ipc_entry_t entry = &table[i];
-
-			if (entry->ie_bits == 0) {
-				entry->ie_bits = IE_BITS_GEN_MASK;
-				entry->ie_next = free_index;
-				free_index = i;
-			}
-		}
-		table[0].ie_next = free_index;
-
-		/*
-		 *	Now we need to free the old table.
-		 *	If the space dies or grows while unlocked,
-		 *	then we can quit here.
-		 */
-
-		is_write_unlock(space);
-		thread_wakeup((event_t) space);
-		it_entries_free(oits, otable);
-		is_write_lock(space);
-		if (!space->is_active || (space->is_table_next != nits))
-			return KERN_SUCCESS;
-
-		/*
-		 *	We might have moved enough entries from
-		 *	the splay tree into the table that
-		 *	the table can be profitably grown again.
-		 *
-		 *	Note that if size == nsize, then
-		 *	space->is_tree_small == 0.
-		 */
-	} while ((space->is_tree_small > 0) &&
-		 (((nsize - size) * sizeof(struct ipc_entry)) <
-		  (space->is_tree_small * sizeof(struct ipc_tree_entry))));
-
-	return KERN_SUCCESS;
+	space->is_size -= 1;
 }
 
 
diff --git a/ipc/ipc_entry.h b/ipc/ipc_entry.h
index 0caa70b..5c1f8fd 100644
--- a/ipc/ipc_entry.h
+++ b/ipc/ipc_entry.h
@@ -48,42 +48,27 @@
 
 /*
  *	Spaces hold capabilities for ipc_object_t's (ports and port sets).
- *	Each ipc_entry_t records a capability.  Most capabilities have
- *	small names, and the entries are elements of a table.
- *	Capabilities can have large names, and a splay tree holds
- *	those entries.  The cutoff point between the table and the tree
- *	is adjusted dynamically to minimize memory consumption.
- *
- *	Free (unallocated) entries in the table have null ie_object
- *	fields.  The ie_bits field is zero except for IE_BITS_GEN.
- *	The ie_next (ie_request) field links free entries into a free list.
- *
- *	The first entry in the table (index 0) is always free.
- *	It is used as the head of the free list.
+ *	Each ipc_entry_t records a capability.
  */
 
 typedef unsigned int ipc_entry_bits_t;
 typedef ipc_table_elems_t ipc_entry_num_t;	/* number of entries */
 
 typedef struct ipc_entry {
+	mach_port_t ie_name;
 	ipc_entry_bits_t ie_bits;
 	struct ipc_object *ie_object;
 	union {
-		mach_port_index_t next;
+		struct ipc_entry *next_free;
 		/*XXX ipc_port_request_index_t request;*/
 		unsigned int request;
 	} index;
-	union {
-		mach_port_index_t table;
-		struct ipc_tree_entry *tree;
-	} hash;
 } *ipc_entry_t;
 
 #define	IE_NULL		((ipc_entry_t) 0)
 
 #define	ie_request	index.request
-#define	ie_next		index.next
-#define	ie_index	hash.table
+#define	ie_next_free	index.next_free
 
 #define	IE_BITS_UREFS_MASK	0x0000ffff	/* 16 bits of user-reference */
 #define	IE_BITS_UREFS(bits)	((bits) & IE_BITS_UREFS_MASK)
@@ -93,12 +78,10 @@ typedef struct ipc_entry {
 
 #define	IE_BITS_MAREQUEST	0x00200000	/* 1 bit for msg-accepted */
 
-#define	IE_BITS_COMPAT		0x00400000	/* 1 bit for compatibility */
-
-#define	IE_BITS_COLLISION	0x00800000	/* 1 bit for collisions */
-#define	IE_BITS_RIGHT_MASK	0x007fffff	/* relevant to the right */
+#define	IE_BITS_RIGHT_MASK	0x003fffff	/* relevant to the right */
 
 #if PORT_GENERATIONS
+#error "not supported"
 #define	IE_BITS_GEN_MASK	0xff000000U	/* 8 bits for generation */
 #define	IE_BITS_GEN(bits)	((bits) & IE_BITS_GEN_MASK)
 #define	IE_BITS_GEN_ONE		0x01000000	/* low bit of generation */
@@ -109,26 +92,9 @@ typedef struct ipc_entry {
 #endif
 
 
-typedef struct ipc_tree_entry {
-	struct ipc_entry ite_entry;
-	mach_port_t ite_name;
-	struct ipc_space *ite_space;
-	struct ipc_tree_entry *ite_lchild;
-	struct ipc_tree_entry *ite_rchild;
-} *ipc_tree_entry_t;
-
-#define	ITE_NULL	((ipc_tree_entry_t) 0)
-
-#define	ite_bits	ite_entry.ie_bits
-#define	ite_object	ite_entry.ie_object
-#define	ite_request	ite_entry.ie_request
-#define	ite_next	ite_entry.hash.tree
-
-extern struct kmem_cache ipc_tree_entry_cache;
-
-#define ite_alloc()	((ipc_tree_entry_t) kmem_cache_alloc(&ipc_tree_entry_cache))
-#define	ite_free(ite)	kmem_cache_free(&ipc_tree_entry_cache, (vm_offset_t) (ite))
-
+extern struct kmem_cache ipc_entry_cache;
+#define ie_alloc()	((ipc_entry_t) kmem_cache_alloc(&ipc_entry_cache))
+#define	ie_free(e)	kmem_cache_free(&ipc_entry_cache, (vm_offset_t) (e))
 
 extern ipc_entry_t
 ipc_entry_lookup(ipc_space_t space, mach_port_t name);
@@ -145,9 +111,6 @@ ipc_entry_alloc_name(ipc_space_t space, mach_port_t name, ipc_entry_t *entryp);
 extern void
 ipc_entry_dealloc(ipc_space_t space, mach_port_t name, ipc_entry_t entry);
 
-extern kern_return_t
-ipc_entry_grow_table(ipc_space_t space);
-
 ipc_entry_t
 db_ipc_object_by_name(
 	task_t		task,
diff --git a/ipc/ipc_hash.c b/ipc/ipc_hash.c
deleted file mode 100644
index 87952a7..0000000
--- a/ipc/ipc_hash.c
+++ /dev/null
@@ -1,486 +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_hash.c
- *	Author:	Rich Draves
- *	Date:	1989
- *
- *	Entry hash table operations.
- */
-
-#include <kern/printf.h>
-#include <mach/boolean.h>
-#include <mach/port.h>
-#include <kern/lock.h>
-#include <kern/kalloc.h>
-#include <ipc/port.h>
-#include <ipc/ipc_space.h>
-#include <ipc/ipc_object.h>
-#include <ipc/ipc_entry.h>
-#include <ipc/ipc_hash.h>
-#include <ipc/ipc_init.h>
-#include <ipc/ipc_types.h>
-
-#if	MACH_IPC_DEBUG
-#include <mach/kern_return.h>
-#include <mach_debug/hash_info.h>
-#include <vm/vm_map.h>
-#include <vm/vm_kern.h>
-#include <vm/vm_user.h>
-#endif
-
-
-
-/*
- *	Routine:	ipc_hash_lookup
- *	Purpose:
- *		Converts (space, obj) -> (name, entry).
- *		Returns TRUE if an entry was found.
- *	Conditions:
- *		The space must be locked (read or write) throughout.
- */
-
-boolean_t
-ipc_hash_lookup(
-	ipc_space_t space,
-	ipc_object_t obj,
-	mach_port_t *namep,
-	ipc_entry_t *entryp)
-{
-	return (ipc_hash_local_lookup(space, obj, namep, entryp) ||
-		((space->is_tree_hash > 0) &&
-		 ipc_hash_global_lookup(space, obj, namep,
-					(ipc_tree_entry_t *) entryp)));
-}
-
-/*
- *	Routine:	ipc_hash_insert
- *	Purpose:
- *		Inserts an entry into the appropriate reverse hash table,
- *		so that ipc_hash_lookup will find it.
- *	Conditions:
- *		The space must be write-locked.
- */
-
-void
-ipc_hash_insert(
-	ipc_space_t	space,
-	ipc_object_t	obj,
-	mach_port_t	name,
-	ipc_entry_t	entry)
-{
-	mach_port_index_t index;
-
-	index = MACH_PORT_INDEX(name);
-	if ((index < space->is_table_size) &&
-	    (entry == &space->is_table[index]))
-		ipc_hash_local_insert(space, obj, index, entry);
-	else
-		ipc_hash_global_insert(space, obj, name,
-				       (ipc_tree_entry_t) entry);
-}
-
-/*
- *	Routine:	ipc_hash_delete
- *	Purpose:
- *		Deletes an entry from the appropriate reverse hash table.
- *	Conditions:
- *		The space must be write-locked.
- */
-
-void
-ipc_hash_delete(
-	ipc_space_t	space,
-	ipc_object_t	obj,
-	mach_port_t	name,
-	ipc_entry_t	entry)
-{
-	mach_port_index_t index;
-
-	index = MACH_PORT_INDEX(name);
-	if ((index < space->is_table_size) &&
-	    (entry == &space->is_table[index]))
-		ipc_hash_local_delete(space, obj, index, entry);
-	else
-		ipc_hash_global_delete(space, obj, name,
-				       (ipc_tree_entry_t) entry);
-}
-
-/*
- *	The global reverse hash table holds splay tree entries.
- *	It is a simple open-chaining hash table with singly-linked buckets.
- *	Each bucket is locked separately, with an exclusive lock.
- *	Within each bucket, move-to-front is used.
- */
-
-ipc_hash_index_t ipc_hash_global_size;
-ipc_hash_index_t ipc_hash_global_mask;
-
-#define IH_GLOBAL_HASH(space, obj)					\
-	(((((ipc_hash_index_t) ((vm_offset_t)space)) >> 4) +		\
-	  (((ipc_hash_index_t) ((vm_offset_t)obj)) >> 6)) &		\
-	 ipc_hash_global_mask)
-
-typedef struct ipc_hash_global_bucket {
-	decl_simple_lock_data(, ihgb_lock_data)
-	ipc_tree_entry_t ihgb_head;
-} *ipc_hash_global_bucket_t;
-
-#define	IHGB_NULL	((ipc_hash_global_bucket_t) 0)
-
-#define	ihgb_lock_init(ihgb)	simple_lock_init(&(ihgb)->ihgb_lock_data)
-#define	ihgb_lock(ihgb)		simple_lock(&(ihgb)->ihgb_lock_data)
-#define	ihgb_unlock(ihgb)	simple_unlock(&(ihgb)->ihgb_lock_data)
-
-ipc_hash_global_bucket_t ipc_hash_global_table;
-
-/*
- *	Routine:	ipc_hash_global_lookup
- *	Purpose:
- *		Converts (space, obj) -> (name, entry).
- *		Looks in the global table, for splay tree entries.
- *		Returns TRUE if an entry was found.
- *	Conditions:
- *		The space must be locked (read or write) throughout.
- */
-
-boolean_t
-ipc_hash_global_lookup(
-	ipc_space_t		space,
-	ipc_object_t		obj,
-	mach_port_t		*namep,
-	ipc_tree_entry_t	*entryp)
-{
-	ipc_hash_global_bucket_t bucket;
-	ipc_tree_entry_t this, *last;
-
-	assert(space != IS_NULL);
-	assert(obj != IO_NULL);
-
-	bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
-	ihgb_lock(bucket);
-
-	if ((this = bucket->ihgb_head) != ITE_NULL) {
-		if ((this->ite_object == obj) &&
-		    (this->ite_space == space)) {
-			/* found it at front; no need to move */
-
-			*namep = this->ite_name;
-			*entryp = this;
-		} else for (last = &this->ite_next;
-			    (this = *last) != ITE_NULL;
-			    last = &this->ite_next) {
-			if ((this->ite_object == obj) &&
-			    (this->ite_space == space)) {
-				/* found it; move to front */
-
-				*last = this->ite_next;
-				this->ite_next = bucket->ihgb_head;
-				bucket->ihgb_head = this;
-
-				*namep = this->ite_name;
-				*entryp = this;
-				break;
-			}
-		}
-	}
-
-	ihgb_unlock(bucket);
-	return this != ITE_NULL;
-}
-
-/*
- *	Routine:	ipc_hash_global_insert
- *	Purpose:
- *		Inserts an entry into the global reverse hash table.
- *	Conditions:
- *		The space must be write-locked.
- */
-
-void
-ipc_hash_global_insert(
-	ipc_space_t		space,
-	ipc_object_t		obj,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry)
-{
-	ipc_hash_global_bucket_t bucket;
-
-
-	assert(entry->ite_name == name);
-	assert(space != IS_NULL);
-	assert(entry->ite_space == space);
-	assert(obj != IO_NULL);
-	assert(entry->ite_object == obj);
-
-	space->is_tree_hash++;
-	assert(space->is_tree_hash <= space->is_tree_total);
-
-	bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
-	ihgb_lock(bucket);
-
-	/* insert at front of bucket */
-
-	entry->ite_next = bucket->ihgb_head;
-	bucket->ihgb_head = entry;
-
-	ihgb_unlock(bucket);
-}
-
-/*
- *	Routine:	ipc_hash_global_delete
- *	Purpose:
- *		Deletes an entry from the global reverse hash table.
- *	Conditions:
- *		The space must be write-locked.
- */
-
-void
-ipc_hash_global_delete(
-	ipc_space_t		space,
-	ipc_object_t		obj,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry)
-{
-	ipc_hash_global_bucket_t bucket;
-	ipc_tree_entry_t this, *last;
-
-	assert(entry->ite_name == name);
-	assert(space != IS_NULL);
-	assert(entry->ite_space == space);
-	assert(obj != IO_NULL);
-	assert(entry->ite_object == obj);
-
-	assert(space->is_tree_hash > 0);
-	space->is_tree_hash--;
-
-	bucket = &ipc_hash_global_table[IH_GLOBAL_HASH(space, obj)];
-	ihgb_lock(bucket);
-
-	for (last = &bucket->ihgb_head;
-	     (this = *last) != ITE_NULL;
-	     last = &this->ite_next) {
-		if (this == entry) {
-			/* found it; remove from bucket */
-
-			*last = this->ite_next;
-			break;
-		}
-	}
-	assert(this != ITE_NULL);
-
-	ihgb_unlock(bucket);
-}
-
-/*
- *	Each space has a local reverse mapping from objects to entries
- *	from the space's table.  This used to be a hash table.
- */
-
-#define IPC_LOCAL_HASH_INVARIANT(S, O, N, E)				\
-	MACRO_BEGIN							\
-	assert(IE_BITS_TYPE((E)->ie_bits) == MACH_PORT_TYPE_SEND ||	\
-	       IE_BITS_TYPE((E)->ie_bits) == MACH_PORT_TYPE_SEND_RECEIVE || \
-	       IE_BITS_TYPE((E)->ie_bits) == MACH_PORT_TYPE_NONE);	\
-	assert((E)->ie_object == (O));					\
-	assert((E)->ie_index == (N));					\
-	assert(&(S)->is_table[N] == (E));				\
-	MACRO_END
-
-/*
- *	Routine:	ipc_hash_local_lookup
- *	Purpose:
- *		Converts (space, obj) -> (name, entry).
- *		Looks in the space's local table, for table entries.
- *		Returns TRUE if an entry was found.
- *	Conditions:
- *		The space must be locked (read or write) throughout.
- */
-
-boolean_t
-ipc_hash_local_lookup(
-	ipc_space_t	space,
-	ipc_object_t	obj,
-	mach_port_t	*namep,
-	ipc_entry_t	*entryp)
-{
-	assert(space != IS_NULL);
-	assert(obj != IO_NULL);
-
-	*entryp = ipc_reverse_lookup(space, obj);
-	if (*entryp != IE_NULL) {
-		*namep = (*entryp)->ie_index;
-		IPC_LOCAL_HASH_INVARIANT(space, obj, *namep, *entryp);
-		return TRUE;
-	}
-	return FALSE;
-}
-
-/*
- *	Routine:	ipc_hash_local_insert
- *	Purpose:
- *		Inserts an entry into the space's reverse hash table.
- *	Conditions:
- *		The space must be write-locked.
- */
-
-void
-ipc_hash_local_insert(
-	ipc_space_t		space,
-	ipc_object_t		obj,
-	mach_port_index_t	index,
-	ipc_entry_t		entry)
-{
-	kern_return_t kr;
-	assert(index != 0);
-	assert(space != IS_NULL);
-	assert(obj != IO_NULL);
-
-	entry->ie_index = index;
-	IPC_LOCAL_HASH_INVARIANT(space, obj, index, entry);
-	kr = ipc_reverse_insert(space, obj, entry);
-	assert(kr == 0);
-}
-
-/*
- *	Routine:	ipc_hash_local_delete
- *	Purpose:
- *		Deletes an entry from the space's reverse hash table.
- *	Conditions:
- *		The space must be write-locked.
- */
-
-void
-ipc_hash_local_delete(
-	ipc_space_t		space,
-	ipc_object_t		obj,
-	mach_port_index_t	index,
-	ipc_entry_t		entry)
-{
-	ipc_entry_t removed;
-	assert(index != MACH_PORT_NULL);
-	assert(space != IS_NULL);
-	assert(obj != IO_NULL);
-
-	IPC_LOCAL_HASH_INVARIANT(space, obj, index, entry);
-	removed = ipc_reverse_remove(space, obj);
-	assert(removed == entry);
-}
-
-/*
- *	Routine:	ipc_hash_init
- *	Purpose:
- *		Initialize the reverse hash table implementation.
- */
-
-void
-ipc_hash_init(void)
-{
-	ipc_hash_index_t i;
-
-	/* initialize ipc_hash_global_size */
-
-	ipc_hash_global_size = IPC_HASH_GLOBAL_SIZE;
-
-	/* make sure it is a power of two */
-
-	ipc_hash_global_mask = ipc_hash_global_size - 1;
-	if ((ipc_hash_global_size & ipc_hash_global_mask) != 0) {
-		natural_t bit;
-
-		/* round up to closest power of two */
-
-		for (bit = 1;; bit <<= 1) {
-			ipc_hash_global_mask |= bit;
-			ipc_hash_global_size = ipc_hash_global_mask + 1;
-
-			if ((ipc_hash_global_size & ipc_hash_global_mask) == 0)
-				break;
-		}
-	}
-
-	/* allocate ipc_hash_global_table */
-
-	ipc_hash_global_table = (ipc_hash_global_bucket_t)
-		kalloc((vm_size_t) (ipc_hash_global_size *
-				    sizeof(struct ipc_hash_global_bucket)));
-	assert(ipc_hash_global_table != IHGB_NULL);
-
-	/* and initialize it */
-
-	for (i = 0; i < ipc_hash_global_size; i++) {
-		ipc_hash_global_bucket_t bucket;
-
-		bucket = &ipc_hash_global_table[i];
-		ihgb_lock_init(bucket);
-		bucket->ihgb_head = ITE_NULL;
-	}
-}
-
-#if	MACH_IPC_DEBUG
-
-/*
- *	Routine:	ipc_hash_info
- *	Purpose:
- *		Return information about the global reverse hash table.
- *		Fills the buffer with as much information as possible
- *		and returns the desired size of the buffer.
- *	Conditions:
- *		Nothing locked.  The caller should provide
- *		possibly-pageable memory.
- */
-
-
-ipc_hash_index_t
-ipc_hash_info(
-	hash_info_bucket_t	*info,
-	mach_msg_type_number_t count)
-{
-	ipc_hash_index_t i;
-
-	if (ipc_hash_global_size < count)
-		count = ipc_hash_global_size;
-
-	for (i = 0; i < count; i++) {
-		ipc_hash_global_bucket_t bucket = &ipc_hash_global_table[i];
-		unsigned int bucket_count = 0;
-		ipc_tree_entry_t entry;
-
-		ihgb_lock(bucket);
-		for (entry = bucket->ihgb_head;
-		     entry != ITE_NULL;
-		     entry = entry->ite_next)
-			bucket_count++;
-		ihgb_unlock(bucket);
-
-		/* don't touch pageable memory while holding locks */
-		info[i].hib_count = bucket_count;
-	}
-
-	return ipc_hash_global_size;
-}
-
-#endif	/* MACH_IPC_DEBUG */
diff --git a/ipc/ipc_hash.h b/ipc/ipc_hash.h
deleted file mode 100644
index 929ba77..0000000
--- a/ipc/ipc_hash.h
+++ /dev/null
@@ -1,96 +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_hash.h
- *	Author:	Rich Draves
- *	Date:	1989
- *
- *	Declarations of entry hash table operations.
- */
-
-#ifndef	_IPC_IPC_HASH_H_
-#define _IPC_IPC_HASH_H_
-
-#include <mach/boolean.h>
-#include <mach/kern_return.h>
-
-typedef natural_t ipc_hash_index_t;
-
-extern void
-ipc_hash_init(void);
-
-#if	MACH_IPC_DEBUG
-
-extern ipc_hash_index_t
-ipc_hash_info(hash_info_bucket_t *, mach_msg_type_number_t);
-
-#endif	/* MACH_IPC_DEBUG */
-
-extern boolean_t
-ipc_hash_lookup(ipc_space_t space, ipc_object_t obj,
-		mach_port_t *namep, ipc_entry_t *entryp);
-
-extern void
-ipc_hash_insert(ipc_space_t space, ipc_object_t obj,
-		mach_port_t name, ipc_entry_t entry);
-
-extern void
-ipc_hash_delete(ipc_space_t space, ipc_object_t obj,
-		mach_port_t name, ipc_entry_t entry);
-
-/*
- *	For use by functions that know what they're doing:
- *	the global primitives, for splay tree entries,
- *	and the local primitives, for table entries.
- */
-
-#define	IPC_HASH_GLOBAL_SIZE	256
-
-extern boolean_t
-ipc_hash_global_lookup(ipc_space_t space, ipc_object_t obj,
-		       mach_port_t *namep, ipc_tree_entry_t *entryp);
-
-extern void
-ipc_hash_global_insert(ipc_space_t space, ipc_object_t obj,
-		       mach_port_t name, ipc_tree_entry_t entry);
-
-extern void
-ipc_hash_global_delete(ipc_space_t space, ipc_object_t obj,
-		       mach_port_t name, ipc_tree_entry_t entry);
-
-extern boolean_t
-ipc_hash_local_lookup(ipc_space_t space, ipc_object_t obj,
-		      mach_port_t *namep, ipc_entry_t *entryp);
-
-extern void
-ipc_hash_local_insert(ipc_space_t space, ipc_object_t obj,
-		      mach_port_index_t index, ipc_entry_t entry);
-
-extern void
-ipc_hash_local_delete(ipc_space_t space, ipc_object_t obj,
-		      mach_port_index_t index, ipc_entry_t entry);
-
-#endif	/* _IPC_IPC_HASH_H_ */
diff --git a/ipc/ipc_init.c b/ipc/ipc_init.c
index debda47..2c58a6e 100644
--- a/ipc/ipc_init.c
+++ b/ipc/ipc_init.c
@@ -47,7 +47,6 @@
 #include <ipc/ipc_marequest.h>
 #include <ipc/ipc_notify.h>
 #include <ipc/ipc_kmsg.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_init.h>
 
 
@@ -76,8 +75,8 @@ ipc_bootstrap(void)
 	kmem_cache_init(&ipc_space_cache, "ipc_space",
 			sizeof(struct ipc_space), 0, NULL, NULL, NULL, 0);
 
-	kmem_cache_init(&ipc_tree_entry_cache, "ipc_tree_entry",
-			sizeof(struct ipc_tree_entry), 0, NULL, NULL, NULL, 0);
+	kmem_cache_init(&ipc_entry_cache, "ipc_entry",
+			sizeof(struct ipc_entry), 0, NULL, NULL, NULL, 0);
 
 	kmem_cache_init(&ipc_object_caches[IOT_PORT], "ipc_port",
 			sizeof(struct ipc_port), 0, NULL, NULL, NULL, 0);
@@ -97,7 +96,6 @@ ipc_bootstrap(void)
 
 	ipc_table_init();
 	ipc_notify_init();
-	ipc_hash_init();
 	ipc_marequest_init();
 }
 
diff --git a/ipc/ipc_kmsg.c b/ipc/ipc_kmsg.c
index cae700f..5076809 100644
--- a/ipc/ipc_kmsg.c
+++ b/ipc/ipc_kmsg.c
@@ -50,7 +50,6 @@
 #include <vm/vm_user.h>
 #include <ipc/port.h>
 #include <ipc/ipc_entry.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_kmsg.h>
 #include <ipc/ipc_thread.h>
 #include <ipc/ipc_marequest.h>
@@ -1774,7 +1773,7 @@ ipc_kmsg_copyout_header(
 			break;
 
 		is_write_lock(space);
-		if (!space->is_active || space->is_table->ie_next == 0) {
+		if (!space->is_active || space->is_free_list == NULL) {
 			is_write_unlock(space);
 			break;
 		}
@@ -2003,28 +2002,20 @@ ipc_kmsg_copyout_header(
 				goto copyout_dest;
 			}
 
-			kr = ipc_entry_get(space, &reply_name, &entry);
+			kr = ipc_entry_alloc(space, &reply_name, &entry);
 			if (kr != KERN_SUCCESS) {
 				ip_unlock(reply);
 
 				if (notify_port != IP_NULL)
 					ipc_port_release_sonce(notify_port);
 
-				/* space is locked */
-				kr = ipc_entry_grow_table(space);
-				if (kr != KERN_SUCCESS) {
-					/* space is unlocked */
-
-					if (kr == KERN_RESOURCE_SHORTAGE)
-						return (MACH_RCV_HEADER_ERROR|
-							MACH_MSG_IPC_KERNEL);
-					else
-						return (MACH_RCV_HEADER_ERROR|
-							MACH_MSG_IPC_SPACE);
-				}
-				/* space is locked again; start over */
-
-				continue;
+				is_write_unlock(space);
+				if (kr == KERN_RESOURCE_SHORTAGE)
+					return (MACH_RCV_HEADER_ERROR|
+					        MACH_MSG_IPC_KERNEL);
+				else
+					return (MACH_RCV_HEADER_ERROR|
+					        MACH_MSG_IPC_SPACE);
 			}
 
 			assert(IE_BITS_TYPE(entry->ie_bits)
@@ -2266,12 +2257,13 @@ ipc_kmsg_copyout_object(
 
 	ip_lock(port);
 	if (!ip_active(port) ||
-	    !ipc_hash_local_lookup(space, (ipc_object_t) port,
-				   namep, &entry)) {
+	    (entry = ipc_reverse_lookup(space,
+	                                (ipc_object_t) port)) == NULL) {
 		ip_unlock(port);
 		is_write_unlock(space);
 		goto slow_copyout;
 	}
+	*namep = entry->ie_name;
 
 	/*
 	 *	Copyout the send right, incrementing urefs
diff --git a/ipc/ipc_object.c b/ipc/ipc_object.c
index db6ef01..2d84cf5 100644
--- a/ipc/ipc_object.c
+++ b/ipc/ipc_object.c
@@ -41,7 +41,6 @@
 #include <ipc/ipc_space.h>
 #include <ipc/ipc_entry.h>
 #include <ipc/ipc_object.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_right.h>
 #include <ipc/ipc_notify.h>
 #include <ipc/ipc_pset.h>
@@ -630,15 +629,10 @@ ipc_object_copyout(
 			break;
 		}
 
-		kr = ipc_entry_get(space, &name, &entry);
+		kr = ipc_entry_alloc(space, &name, &entry);
 		if (kr != KERN_SUCCESS) {
-			/* unlocks/locks space, so must start again */
-
-			kr = ipc_entry_grow_table(space);
-			if (kr != KERN_SUCCESS)
-				return kr; /* space is unlocked */
-
-			continue;
+			is_write_unlock(space);
+			return kr;
 		}
 
 		assert(IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_NONE);
@@ -691,15 +685,10 @@ ipc_object_copyout_multiname(space, object, namep)
 			return KERN_INVALID_TASK;
 		}
 
-		kr = ipc_entry_get(space, &name, &entry);
+		kr = ipc_entry_alloc(space, &name, &entry);
 		if (kr != KERN_SUCCESS) {
-			/* unlocks/locks space, so must start again */
-
-			kr = ipc_entry_grow_table(space);
-			if (kr != KERN_SUCCESS)
-				return kr; /* space is unlocked */
-
-			continue;
+			is_write_unlock(space);
+			return kr; /* space is unlocked */
 		}
 
 		assert(IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_NONE);
diff --git a/ipc/ipc_right.c b/ipc/ipc_right.c
index 35061c9..773b3b1 100644
--- a/ipc/ipc_right.c
+++ b/ipc/ipc_right.c
@@ -43,7 +43,6 @@
 #include <ipc/ipc_entry.h>
 #include <ipc/ipc_space.h>
 #include <ipc/ipc_object.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_port.h>
 #include <ipc/ipc_pset.h>
 #include <ipc/ipc_marequest.h>
@@ -142,7 +141,8 @@ ipc_right_reverse(
 		return TRUE;
 	}
 
-	if (ipc_hash_lookup(space, (ipc_object_t) port, namep, entryp)) {
+	if ((*entryp = ipc_reverse_lookup(space, (ipc_object_t) port))) {
+		*namep = (*entryp)->ie_name;
 		assert((entry = *entryp) != IE_NULL);
 		assert(IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_SEND);
 		assert(port == (ipc_port_t) entry->ie_object);
@@ -392,7 +392,7 @@ ipc_right_check(
 			ipc_marequest_cancel(space, name);
 		}
 
-		ipc_hash_delete(space, (ipc_object_t) port, name, entry);
+		ipc_reverse_remove(space, (ipc_object_t) port);
 	} else {
 		assert(IE_BITS_TYPE(bits) == MACH_PORT_TYPE_SEND_ONCE);
 		assert(IE_BITS_UREFS(bits) == 1);
@@ -609,8 +609,7 @@ ipc_right_destroy(
 		}
 
 		if (type == MACH_PORT_TYPE_SEND)
-			ipc_hash_delete(space, (ipc_object_t) port,
-					name, entry);
+			ipc_reverse_remove(space, (ipc_object_t) port);
 
 		ip_lock(port);
 
@@ -789,8 +788,7 @@ ipc_right_dealloc(
 			dnrequest = ipc_right_dncancel_macro(space, port,
 							     name, entry);
 
-			ipc_hash_delete(space, (ipc_object_t) port,
-					name, entry);
+			ipc_reverse_remove(space, (ipc_object_t) port);
 
 			if (bits & IE_BITS_MAREQUEST)
 				ipc_marequest_cancel(space, name);
@@ -1134,8 +1132,7 @@ ipc_right_delta(
 				dnrequest = ipc_right_dncancel_macro(
 						space, port, name, entry);
 
-				ipc_hash_delete(space, (ipc_object_t) port,
-						name, entry);
+				ipc_reverse_remove(space, (ipc_object_t) port);
 
 				if (bits & IE_BITS_MAREQUEST)
 					ipc_marequest_cancel(space, name);
@@ -1410,8 +1407,8 @@ ipc_right_copyin(
 			assert(IE_BITS_UREFS(bits) > 0);
 			assert(port->ip_srights > 0);
 
-			ipc_hash_insert(space, (ipc_object_t) port,
-					name, entry);
+			entry->ie_name = name;
+			ipc_reverse_insert(space, (ipc_object_t) port, entry);
 
 			ip_reference(port);
 		} else {
@@ -1534,8 +1531,7 @@ ipc_right_copyin(
 				dnrequest = ipc_right_dncancel_macro(
 						space, port, name, entry);
 
-				ipc_hash_delete(space, (ipc_object_t) port,
-						name, entry);
+				ipc_reverse_remove(space, (ipc_object_t) port);
 
 				if (bits & IE_BITS_MAREQUEST)
 					ipc_marequest_cancel(space, name);
@@ -1796,8 +1792,7 @@ ipc_right_copyin_two(
 			dnrequest = ipc_right_dncancel_macro(space, port,
 							     name, entry);
 
-			ipc_hash_delete(space, (ipc_object_t) port,
-					name, entry);
+			ipc_reverse_remove(space, (ipc_object_t) port);
 
 			if (bits & IE_BITS_MAREQUEST)
 				ipc_marequest_cancel(space, name);
@@ -1921,8 +1916,8 @@ ipc_right_copyout(
 
 			/* entry is locked holding ref, so can use port */
 
-			ipc_hash_insert(space, (ipc_object_t) port,
-					name, entry);
+			entry->ie_name = name;
+			ipc_reverse_insert(space, (ipc_object_t) port, entry);
 		}
 
 		entry->ie_bits = (bits | MACH_PORT_TYPE_SEND) + 1;
@@ -1956,8 +1951,7 @@ ipc_right_copyout(
 
 			/* entry is locked holding ref, so can use port */
 
-			ipc_hash_delete(space, (ipc_object_t) port,
-					name, entry);
+			ipc_reverse_remove(space, (ipc_object_t) port);
 		} else {
 			assert(IE_BITS_TYPE(bits) == MACH_PORT_TYPE_NONE);
 			assert(IE_BITS_UREFS(bits) == 0);
@@ -2083,7 +2077,7 @@ ipc_right_rename(
 		ipc_marequest_rename(space, oname, nname);
 	}
 
-	/* initialize nentry before letting ipc_hash_insert see it */
+	/* initialize nentry before letting ipc_reverse_insert see it */
 
 	assert((nentry->ie_bits & IE_BITS_RIGHT_MASK) == 0);
 	nentry->ie_bits |= bits & IE_BITS_RIGHT_MASK;
@@ -2097,8 +2091,9 @@ ipc_right_rename(
 		port = (ipc_port_t) object;
 		assert(port != IP_NULL);
 
-		ipc_hash_delete(space, (ipc_object_t) port, oname, oentry);
-		ipc_hash_insert(space, (ipc_object_t) port, nname, nentry);
+		ipc_reverse_remove(space, (ipc_object_t) port);
+		nentry->ie_name = nname;
+		ipc_reverse_insert(space, (ipc_object_t) port, nentry);
 		break;
 	    }
 
diff --git a/ipc/ipc_space.c b/ipc/ipc_space.c
index dcc96b3..ea3cb3b 100644
--- a/ipc/ipc_space.c
+++ b/ipc/ipc_space.c
@@ -46,8 +46,6 @@
 #include <kern/slab.h>
 #include <ipc/port.h>
 #include <ipc/ipc_entry.h>
-#include <ipc/ipc_splay.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_table.h>
 #include <ipc/ipc_port.h>
 #include <ipc/ipc_space.h>
@@ -82,6 +80,9 @@ ipc_space_release(
 	ipc_space_release_macro(space);
 }
 
+/* A place-holder object for the zeroth entry.  */
+struct ipc_entry zero_entry;
+
 /*
  *	Routine:	ipc_space_create
  *	Purpose:
@@ -102,53 +103,24 @@ ipc_space_create(
 	ipc_space_t		*spacep)
 {
 	ipc_space_t space;
-	ipc_entry_t table;
-	ipc_entry_num_t new_size;
-	mach_port_index_t index;
 
 	space = is_alloc();
 	if (space == IS_NULL)
 		return KERN_RESOURCE_SHORTAGE;
 
-	table = it_entries_alloc(initial);
-	if (table == IE_NULL) {
-		is_free(space);
-		return KERN_RESOURCE_SHORTAGE;
-	}
-
-	new_size = initial->its_size;
-	memset((void *) table, 0, new_size * sizeof(struct ipc_entry));
-
-	/*
-	 *	Initialize the free list in the table.
-	 *	Add the entries in reverse order, and
-	 *	set the generation number to -1, so that
-	 *	initial allocations produce "natural" names.
-	 */
-
-	for (index = 0; index < new_size; index++) {
-		ipc_entry_t entry = &table[index];
-
-		entry->ie_bits = IE_BITS_GEN_MASK;
-		entry->ie_next = index+1;
-	}
-	table[new_size-1].ie_next = 0;
-
 	is_ref_lock_init(space);
 	space->is_references = 2;
 
 	is_lock_init(space);
 	space->is_active = TRUE;
-	space->is_growing = FALSE;
-	space->is_table = table;
-	space->is_table_size = new_size;
-	space->is_table_next = initial+1;
-
-	ipc_splay_tree_init(&space->is_tree);
-	space->is_tree_total = 0;
-	space->is_tree_small = 0;
-	space->is_tree_hash = 0;
+
+	rdxtree_init(&space->is_map);
 	rdxtree_init(&space->is_reverse_map);
+	/* The zeroth entry is reserved.  */
+	rdxtree_insert(&space->is_map, 0, &zero_entry);
+	space->is_size = 1;
+	space->is_free_list = NULL;
+	space->is_free_list_size = 0;
 
 	*spacep = space;
 	return KERN_SUCCESS;
@@ -202,10 +174,6 @@ void
 ipc_space_destroy(
 	ipc_space_t	space)
 {
-	ipc_tree_entry_t tentry;
-	ipc_entry_t table;
-	ipc_entry_num_t size;
-	mach_port_index_t index;
 	boolean_t active;
 
 	assert(space != IS_NULL);
@@ -218,60 +186,24 @@ ipc_space_destroy(
 	if (!active)
 		return;
 
-	/*
-	 *	If somebody is trying to grow the table,
-	 *	we must wait until they finish and figure
-	 *	out the space died.
-	 */
+	ipc_entry_t entry;
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&space->is_map, &iter, entry) {
+		if (entry->ie_name == MACH_PORT_NULL)
+			continue;
 
-	is_read_lock(space);
-	while (space->is_growing) {
-		assert_wait((event_t) space, FALSE);
-		is_read_unlock(space);
-		thread_block((void (*)(void)) 0);
-		is_read_lock(space);
-	}
-	is_read_unlock(space);
-
-	/*
-	 *	Now we can futz with it	without having it locked.
-	 */
-
-	table = space->is_table;
-	size = space->is_table_size;
-
-	for (index = 0; index < size; index++) {
-		ipc_entry_t entry = &table[index];
 		mach_port_type_t type = IE_BITS_TYPE(entry->ie_bits);
 
 		if (type != MACH_PORT_TYPE_NONE) {
 			mach_port_t name =
-				MACH_PORT_MAKEB(index, entry->ie_bits);
+				MACH_PORT_MAKEB(entry->ie_name, entry->ie_bits);
 
 			ipc_right_clean(space, name, entry);
 		}
-	}
 
-	it_entries_free(space->is_table_next-1, table);
-
-	for (tentry = ipc_splay_traverse_start(&space->is_tree);
-	     tentry != ITE_NULL;
-	     tentry = ipc_splay_traverse_next(&space->is_tree, TRUE)) {
-		mach_port_type_t type = IE_BITS_TYPE(tentry->ite_bits);
-		mach_port_t name = tentry->ite_name;
-
-		assert(type != MACH_PORT_TYPE_NONE);
-
-		/* use object before ipc_right_clean releases ref */
-
-		if (type == MACH_PORT_TYPE_SEND)
-			ipc_hash_global_delete(space, tentry->ite_object,
-					       name, tentry);
-
-		ipc_right_clean(space, name, &tentry->ite_entry);
+		ie_free(entry);
 	}
-	ipc_splay_traverse_finish(&space->is_tree);
-
+	rdxtree_remove_all(&space->is_map);
 	rdxtree_remove_all(&space->is_reverse_map);
 
 	/*
diff --git a/ipc/ipc_space.h b/ipc/ipc_space.h
index f41c64c..20b9d57 100644
--- a/ipc/ipc_space.h
+++ b/ipc/ipc_space.h
@@ -47,7 +47,7 @@
 #include <kern/lock.h>
 #include <kern/rdxtree.h>
 #include <kern/slab.h>
-#include <ipc/ipc_splay.h>
+#include <ipc/ipc_entry.h>
 #include <ipc/ipc_types.h>
 
 /*
@@ -73,18 +73,16 @@ struct ipc_space {
 
 	decl_simple_lock_data(,is_lock_data)
 	boolean_t is_active;		/* is the space alive? */
-	boolean_t is_growing;		/* is the space growing? */
-	ipc_entry_t is_table;		/* an array of entries */
-	ipc_entry_num_t is_table_size;	/* current size of table */
-	struct ipc_table_size *is_table_next; /* info for larger table */
-	struct ipc_splay_tree is_tree;	/* a splay tree of entries */
-	ipc_entry_num_t is_tree_total;	/* number of entries in the tree */
-	ipc_entry_num_t is_tree_small;	/* # of small entries in the tree */
-	ipc_entry_num_t is_tree_hash;	/* # of hashed entries in the tree */
+	struct rdxtree is_map;		/* a map of entries */
+	size_t is_size;			/* number of entries */
 	struct rdxtree is_reverse_map;	/* maps objects to entries */
-
+	ipc_entry_t is_free_list;	/* a linked list of free entries */
+	size_t is_free_list_size;	/* number of free entries */
+#define IS_FREE_LIST_SIZE_LIMIT	64	/* maximum number of entries
+					   in the free list */
 };
 
+
 #define	IS_NULL			((ipc_space_t) 0)
 
 extern struct kmem_cache ipc_space_cache;
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);
-}
-
diff --git a/ipc/ipc_splay.h b/ipc/ipc_splay.h
deleted file mode 100644
index 42e5a80..0000000
--- a/ipc/ipc_splay.h
+++ /dev/null
@@ -1,114 +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.h
- *	Author:	Rich Draves
- *	Date:	1989
- *
- *	Declarations of primitive splay tree operations.
- */
-
-#ifndef	_IPC_IPC_SPLAY_H_
-#define _IPC_IPC_SPLAY_H_
-
-#include <mach/port.h>
-#include <kern/assert.h>
-#include <kern/macros.h>
-#include <ipc/ipc_entry.h>
-
-typedef struct ipc_splay_tree {
-	mach_port_t ist_name;		/* name used in last lookup */
-	ipc_tree_entry_t ist_root;	/* root of middle tree */
-	ipc_tree_entry_t ist_ltree;	/* root of left tree */
-	ipc_tree_entry_t *ist_ltreep;	/* pointer into left tree */
-	ipc_tree_entry_t ist_rtree;	/* root of right tree */
-	ipc_tree_entry_t *ist_rtreep;	/* pointer into right tree */
-} *ipc_splay_tree_t;
-
-#define	ist_lock(splay)		/* no locking */
-#define ist_unlock(splay)	/* no locking */
-
-/* Initialize a raw splay tree */
-extern void ipc_splay_tree_init(
-	ipc_splay_tree_t	splay);
-
-/* Pick a random entry in a splay tree */
-extern boolean_t ipc_splay_tree_pick(
-	ipc_splay_tree_t	splay,
-	mach_port_t		*namep,
-	ipc_tree_entry_t	*entryp);
-
-/* Find an entry in a splay tree */
-extern ipc_tree_entry_t ipc_splay_tree_lookup(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name);
-
-/* Insert a new entry into a splay tree */
-extern void ipc_splay_tree_insert(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry);
-
-/* Delete an entry from a splay tree */
-extern void ipc_splay_tree_delete(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry);
-
-/* Split a splay tree */
-extern void ipc_splay_tree_split(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_splay_tree_t	entry);
-
-/* Join two splay trees */
-extern void ipc_splay_tree_join(
-	ipc_splay_tree_t	splay,
-	ipc_splay_tree_t	small);
-
-/* Do a bounded splay tree lookup */
-extern void ipc_splay_tree_bounds(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	mach_port_t		*lowerp, 
-	mach_port_t		*upperp);
-
-/* Initialize a symmetric order traversal of a splay tree */
-extern ipc_tree_entry_t ipc_splay_traverse_start(
-	ipc_splay_tree_t	splay);
-
-/* Return the next entry in a symmetric order traversal of a splay tree */
-extern ipc_tree_entry_t ipc_splay_traverse_next(
-	ipc_splay_tree_t	splay,
-	boolean_t		delete);
-
-/* Terminate a symmetric order traversal of a splay tree */
-extern void ipc_splay_traverse_finish(
-	ipc_splay_tree_t	splay);
-
-#endif	/* _IPC_IPC_SPLAY_H_ */
diff --git a/ipc/mach_debug.c b/ipc/mach_debug.c
index eb52e1c..efb07a4 100644
--- a/ipc/mach_debug.c
+++ b/ipc/mach_debug.c
@@ -46,7 +46,6 @@
 #include <vm/vm_kern.h>
 #include <ipc/ipc_space.h>
 #include <ipc/ipc_port.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_marequest.h>
 #include <ipc/ipc_table.h>
 #include <ipc/ipc_right.h>
@@ -94,85 +93,6 @@ mach_port_get_srights(
 }
 
 /*
- *	Routine:	host_ipc_hash_info
- *	Purpose:
- *		Return information about the global reverse hash table.
- *	Conditions:
- *		Nothing locked.  Obeys CountInOut protocol.
- *	Returns:
- *		KERN_SUCCESS		Returned information.
- *		KERN_INVALID_HOST	The host is null.
- *		KERN_RESOURCE_SHORTAGE	Couldn't allocate memory.
- */
-
-kern_return_t
-host_ipc_hash_info(
-	host_t				host,
-	hash_info_bucket_array_t	*infop,
-	mach_msg_type_number_t 		*countp)
-{
-	vm_offset_t addr;
-	vm_size_t size = 0;	/* Suppress gcc warning */
-	hash_info_bucket_t *info;
-	unsigned int potential, actual;
-	kern_return_t kr;
-
-	if (host == HOST_NULL)
-		return KERN_INVALID_HOST;
-
-	/* start with in-line data */
-
-	info = *infop;
-	potential = *countp;
-
-	for (;;) {
-		actual = ipc_hash_info(info, potential);
-		if (actual <= potential)
-			break;
-
-		/* allocate more memory */
-
-		if (info != *infop)
-			kmem_free(ipc_kernel_map, addr, size);
-
-		size = round_page(actual * sizeof *info);
-		kr = kmem_alloc_pageable(ipc_kernel_map, &addr, size);
-		if (kr != KERN_SUCCESS)
-			return KERN_RESOURCE_SHORTAGE;
-
-		info = (hash_info_bucket_t *) addr;
-		potential = size/sizeof *info;
-	}
-
-	if (info == *infop) {
-		/* data fit in-line; nothing to deallocate */
-
-		*countp = actual;
-	} else if (actual == 0) {
-		kmem_free(ipc_kernel_map, addr, size);
-
-		*countp = 0;
-	} else {
-		vm_map_copy_t copy;
-		vm_size_t used;
-
-		used = round_page(actual * sizeof *info);
-
-		if (used != size)
-			kmem_free(ipc_kernel_map, addr + used, size - used);
-
-		kr = vm_map_copyin(ipc_kernel_map, addr, used,
-				   TRUE, &copy);
-		assert(kr == KERN_SUCCESS);
-
-		*infop = (hash_info_bucket_t *) copy;
-		*countp = actual;
-	}
-
-	return KERN_SUCCESS;
-}
-
-/*
  *	Routine:	host_ipc_marequest_info
  *	Purpose:
  *		Return information about the marequest hash table.
@@ -253,251 +173,6 @@ host_ipc_marequest_info(
 }
 
 /*
- *	Routine:	mach_port_space_info
- *	Purpose:
- *		Returns information about an IPC space.
- *	Conditions:
- *		Nothing locked.  Obeys CountInOut protocol.
- *	Returns:
- *		KERN_SUCCESS		Returned information.
- *		KERN_INVALID_TASK	The space is null.
- *		KERN_INVALID_TASK	The space is dead.
- *		KERN_RESOURCE_SHORTAGE	Couldn't allocate memory.
- */
-
-kern_return_t
-mach_port_space_info(
-	ipc_space_t			space,
-	ipc_info_space_t		*infop,
-	ipc_info_name_array_t		*tablep,
-	mach_msg_type_number_t 		*tableCntp,
-	ipc_info_tree_name_array_t	*treep,
-	mach_msg_type_number_t 		*treeCntp)
-{
-	ipc_info_name_t *table_info;
-	unsigned int table_potential, table_actual;
-	vm_offset_t table_addr;
-	vm_size_t table_size = 0;	/* Suppress gcc warning */
-	ipc_info_tree_name_t *tree_info;
-	unsigned int tree_potential, tree_actual;
-	vm_offset_t tree_addr;
-	vm_size_t tree_size = 0;	/* Suppress gcc warning */
-	ipc_tree_entry_t tentry;
-	ipc_entry_t table;
-	ipc_entry_num_t tsize;
-	mach_port_index_t index;
-	kern_return_t kr;
-
-	if (space == IS_NULL)
-		return KERN_INVALID_TASK;
-
-	/* start with in-line memory */
-
-	table_info = *tablep;
-	table_potential = *tableCntp;
-	tree_info = *treep;
-	tree_potential = *treeCntp;
-
-	for (;;) {
-		is_read_lock(space);
-		if (!space->is_active) {
-			is_read_unlock(space);
-			if (table_info != *tablep)
-				kmem_free(ipc_kernel_map,
-					  table_addr, table_size);
-			if (tree_info != *treep)
-				kmem_free(ipc_kernel_map,
-					  tree_addr, tree_size);
-			return KERN_INVALID_TASK;
-		}
-
-		table_actual = space->is_table_size;
-		tree_actual = space->is_tree_total;
-
-		if ((table_actual <= table_potential) &&
-		    (tree_actual <= tree_potential))
-			break;
-
-		is_read_unlock(space);
-
-		if (table_actual > table_potential) {
-			if (table_info != *tablep)
-				kmem_free(ipc_kernel_map,
-					  table_addr, table_size);
-
-			table_size = round_page(table_actual *
-						sizeof *table_info);
-			kr = kmem_alloc(ipc_kernel_map,
-					&table_addr, table_size);
-			if (kr != KERN_SUCCESS) {
-				if (tree_info != *treep)
-					kmem_free(ipc_kernel_map,
-						  tree_addr, tree_size);
-
-				return KERN_RESOURCE_SHORTAGE;
-			}
-
-			table_info = (ipc_info_name_t *) table_addr;
-			table_potential = table_size/sizeof *table_info;
-		}
-
-		if (tree_actual > tree_potential) {
-			if (tree_info != *treep)
-				kmem_free(ipc_kernel_map,
-					  tree_addr, tree_size);
-
-			tree_size = round_page(tree_actual *
-					       sizeof *tree_info);
-			kr = kmem_alloc(ipc_kernel_map,
-					&tree_addr, tree_size);
-			if (kr != KERN_SUCCESS) {
-				if (table_info != *tablep)
-					kmem_free(ipc_kernel_map,
-						  table_addr, table_size);
-
-				return KERN_RESOURCE_SHORTAGE;
-			}
-
-			tree_info = (ipc_info_tree_name_t *) tree_addr;
-			tree_potential = tree_size/sizeof *tree_info;
-		}
-	}
-	/* space is read-locked and active; we have enough wired memory */
-
-	infop->iis_genno_mask = MACH_PORT_NGEN(MACH_PORT_DEAD);
-	infop->iis_table_size = space->is_table_size;
-	infop->iis_table_next = space->is_table_next->its_size;
-	infop->iis_tree_size = space->is_tree_total;
-	infop->iis_tree_small = space->is_tree_small;
-	infop->iis_tree_hash = space->is_tree_hash;
-
-	table = space->is_table;
-	tsize = space->is_table_size;
-
-	for (index = 0; index < tsize; index++) {
-		ipc_info_name_t *iin = &table_info[index];
-		ipc_entry_t entry = &table[index];
-		ipc_entry_bits_t bits = entry->ie_bits;
-
-		iin->iin_name = MACH_PORT_MAKEB(index, bits);
-		iin->iin_collision = (bits & IE_BITS_COLLISION) ? TRUE : FALSE;
-		iin->iin_compat = FALSE;
-		iin->iin_marequest = (bits & IE_BITS_MAREQUEST) ? TRUE : FALSE;
-		iin->iin_type = IE_BITS_TYPE(bits);
-		iin->iin_urefs = IE_BITS_UREFS(bits);
-		iin->iin_object = (vm_offset_t) entry->ie_object;
-		iin->iin_next = entry->ie_next;
-		iin->iin_hash = entry->ie_index;
-	}
-
-	for (tentry = ipc_splay_traverse_start(&space->is_tree), index = 0;
-	     tentry != ITE_NULL;
-	     tentry = ipc_splay_traverse_next(&space->is_tree, FALSE)) {
-		ipc_info_tree_name_t *iitn = &tree_info[index++];
-		ipc_info_name_t *iin = &iitn->iitn_name;
-		ipc_entry_t entry = &tentry->ite_entry;
-		ipc_entry_bits_t bits = entry->ie_bits;
-
-		assert(IE_BITS_TYPE(bits) != MACH_PORT_TYPE_NONE);
-
-		iin->iin_name = tentry->ite_name;
-		iin->iin_collision = (bits & IE_BITS_COLLISION) ? TRUE : FALSE;
-		iin->iin_compat = FALSE;
-		iin->iin_marequest = (bits & IE_BITS_MAREQUEST) ? TRUE : FALSE;
-		iin->iin_type = IE_BITS_TYPE(bits);
-		iin->iin_urefs = IE_BITS_UREFS(bits);
-		iin->iin_object = (vm_offset_t) entry->ie_object;
-		iin->iin_next = entry->ie_next;
-		iin->iin_hash = entry->ie_index;
-
-		if (tentry->ite_lchild == ITE_NULL)
-			iitn->iitn_lchild = MACH_PORT_NULL;
-		else
-			iitn->iitn_lchild = tentry->ite_lchild->ite_name;
-
-		if (tentry->ite_rchild == ITE_NULL)
-			iitn->iitn_rchild = MACH_PORT_NULL;
-		else
-			iitn->iitn_rchild = tentry->ite_rchild->ite_name;
-
-	}
-	ipc_splay_traverse_finish(&space->is_tree);
-	is_read_unlock(space);
-
-	if (table_info == *tablep) {
-		/* data fit in-line; nothing to deallocate */
-
-		*tableCntp = table_actual;
-	} else if (table_actual == 0) {
-		kmem_free(ipc_kernel_map, table_addr, table_size);
-
-		*tableCntp = 0;
-	} else {
-		vm_size_t size_used, rsize_used;
-		vm_map_copy_t copy;
-
-		/* kmem_alloc doesn't zero memory */
-
-		size_used = table_actual * sizeof *table_info;
-		rsize_used = round_page(size_used);
-
-		if (rsize_used != table_size)
-			kmem_free(ipc_kernel_map,
-				  table_addr + rsize_used,
-				  table_size - rsize_used);
-
-		if (size_used != rsize_used)
-			memset((void *) (table_addr + size_used), 0,
-			      rsize_used - size_used);
-
-		kr = vm_map_copyin(ipc_kernel_map, table_addr, rsize_used,
-				   TRUE, &copy);
-
-		assert(kr == KERN_SUCCESS);
-
-		*tablep = (ipc_info_name_t *) copy;
-		*tableCntp = table_actual;
-	}
-
-	if (tree_info == *treep) {
-		/* data fit in-line; nothing to deallocate */
-
-		*treeCntp = tree_actual;
-	} else if (tree_actual == 0) {
-		kmem_free(ipc_kernel_map, tree_addr, tree_size);
-
-		*treeCntp = 0;
-	} else {
-		vm_size_t size_used, rsize_used;
-		vm_map_copy_t copy;
-
-		/* kmem_alloc doesn't zero memory */
-
-		size_used = tree_actual * sizeof *tree_info;
-		rsize_used = round_page(size_used);
-
-		if (rsize_used != tree_size)
-			kmem_free(ipc_kernel_map,
-				  tree_addr + rsize_used,
-				  tree_size - rsize_used);
-
-		if (size_used != rsize_used)
-			memset((void *) (tree_addr + size_used), 0,
-			      rsize_used - size_used);
-
-		kr = vm_map_copyin(ipc_kernel_map, tree_addr, rsize_used,
-				   TRUE, &copy);
-
-		assert(kr == KERN_SUCCESS);
-
-		*treep = (ipc_info_tree_name_t *) copy;
-		*treeCntp = tree_actual;
-	}
-
-	return KERN_SUCCESS;
-}
-
-/*
  *	Routine:	mach_port_dnrequest_info
  *	Purpose:
  *		Returns information about the dead-name requests
diff --git a/ipc/mach_port.c b/ipc/mach_port.c
index 4e89527..93a1248 100644
--- a/ipc/mach_port.c
+++ b/ipc/mach_port.c
@@ -150,10 +150,6 @@ mach_port_names(
 	mach_port_type_t	**typesp,
 	mach_msg_type_number_t	*typesCnt)
 {
-	ipc_tree_entry_t tentry;
-	ipc_entry_t table;
-	ipc_entry_num_t tsize;
-	mach_port_index_t index;
 	ipc_entry_num_t actual;	/* this many names */
 	ipc_port_timestamp_t timestamp;	/* logical time of this operation */
 	mach_port_t *names;
@@ -190,7 +186,7 @@ mach_port_names(
 
 		/* upper bound on number of names in the space */
 
-		bound = space->is_table_size + space->is_tree_total;
+		bound = space->is_size;
 		size_needed = round_page(bound * sizeof(mach_port_t));
 
 		if (size_needed <= size)
@@ -235,33 +231,16 @@ mach_port_names(
 
 	timestamp = ipc_port_timestamp();
 
-	table = space->is_table;
-	tsize = space->is_table_size;
-
-	for (index = 0; index < tsize; index++) {
-		ipc_entry_t entry = &table[index];
+	ipc_entry_t entry;
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&space->is_map, &iter, entry) {
 		ipc_entry_bits_t bits = entry->ie_bits;
 
 		if (IE_BITS_TYPE(bits) != MACH_PORT_TYPE_NONE) {
-			mach_port_t name = MACH_PORT_MAKEB(index, bits);
-
-			mach_port_names_helper(timestamp, entry, name,
+			mach_port_names_helper(timestamp, entry, entry->ie_name,
 					       names, types, &actual);
 		}
 	}
-
-	for (tentry = ipc_splay_traverse_start(&space->is_tree);
-	     tentry != ITE_NULL;
-	     tentry = ipc_splay_traverse_next(&space->is_tree, FALSE)) {
-		ipc_entry_t entry = &tentry->ite_entry;
-		mach_port_t name = tentry->ite_name;
-
-		assert(IE_BITS_TYPE(tentry->ite_bits) != MACH_PORT_TYPE_NONE);
-
-		mach_port_names_helper(timestamp, entry, name,
-				       names, types, &actual);
-	}
-	ipc_splay_traverse_finish(&space->is_tree);
 	is_read_unlock(space);
 
 	if (actual == 0) {
@@ -946,10 +925,7 @@ mach_port_get_set_status(
 	size = PAGE_SIZE;	/* initial guess */
 
 	for (;;) {
-		ipc_tree_entry_t tentry;
-		ipc_entry_t entry, table;
-		ipc_entry_num_t tsize;
-		mach_port_index_t index;
+		ipc_entry_t entry;
 		mach_port_t *names;
 		ipc_pset_t pset;
 
@@ -986,11 +962,9 @@ mach_port_get_set_status(
 		maxnames = size / sizeof(mach_port_t);
 		actual = 0;
 
-		table = space->is_table;
-		tsize = space->is_table_size;
-
-		for (index = 0; index < tsize; index++) {
-			ipc_entry_t ientry = &table[index];
+		ipc_entry_t ientry;
+		struct rdxtree_iter iter;
+		rdxtree_for_each(&space->is_map, &iter, ientry) {
 			ipc_entry_bits_t bits = ientry->ie_bits;
 
 			if (bits & MACH_PORT_TYPE_RECEIVE) {
@@ -1002,22 +976,6 @@ mach_port_get_set_status(
 			}
 		}
 
-		for (tentry = ipc_splay_traverse_start(&space->is_tree);
-		     tentry != ITE_NULL;
-		     tentry = ipc_splay_traverse_next(&space->is_tree,FALSE)) {
-			ipc_entry_bits_t bits = tentry->ite_bits;
-
-			assert(IE_BITS_TYPE(bits) != MACH_PORT_TYPE_NONE);
-
-			if (bits & MACH_PORT_TYPE_RECEIVE) {
-				ipc_port_t port =
-					(ipc_port_t) tentry->ite_object;
-
-				mach_port_gst_helper(pset, port, maxnames,
-						     names, &actual);
-			}
-		}
-		ipc_splay_traverse_finish(&space->is_tree);
 		is_read_unlock(space);
 
 		if (actual <= maxnames)
diff --git a/ipc/port.h b/ipc/port.h
index d359115..49af6e2 100644
--- a/ipc/port.h
+++ b/ipc/port.h
@@ -45,10 +45,7 @@
  *	mach_port_t must be an unsigned type.  Port values
  *	have two parts, a generation number and an index.
  *	These macros encapsulate all knowledge of how
- *	a mach_port_t is laid out.  However, ipc/ipc_entry.c
- *	implicitly assumes when it uses the splay tree functions
- *	that the generation number is in the low bits, so that
- *	names are ordered first by index and then by generation.
+ *	a mach_port_t is laid out.
  *
  *	If the size of generation numbers changes,
  *	be sure to update IE_BITS_GEN_MASK and friends