ipc: replace the IPC table with a radix tree

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

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

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

1 files changed, 18 insertions, 86 deletions

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);
 
 	/*