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.

3 files changed, 3 insertions, 48 deletions

diff --git a/include/mach_debug/ipc_info.h b/include/mach_debug/ipc_info.h
index ef0b0c6..a47ae7b 100644
--- a/include/mach_debug/ipc_info.h
+++ b/include/mach_debug/ipc_info.h
@@ -43,40 +43,17 @@
  *	in mach_debug_types.defs when adding/removing fields.
  */
 
-
-typedef struct ipc_info_space {
-	natural_t iis_genno_mask;	/* generation number mask */
-	natural_t iis_table_size;	/* size of table */
-	natural_t iis_table_next;	/* next possible size of table */
-	natural_t iis_tree_size;	/* size of tree */
-	natural_t iis_tree_small;	/* # of small entries in tree */
-	natural_t iis_tree_hash;	/* # of hashed entries in tree */
-} ipc_info_space_t;
-
-
 typedef struct ipc_info_name {
 	mach_port_t iin_name;		/* port name, including gen number */
-/*boolean_t*/integer_t iin_collision;	/* collision at this entry? */
-/*boolean_t*/integer_t iin_compat;	/* is this a compat-mode entry? */
 /*boolean_t*/integer_t iin_marequest;	/* extant msg-accepted request? */
 	mach_port_type_t iin_type;	/* straight port type */
 	mach_port_urefs_t iin_urefs;	/* user-references */
 	vm_offset_t iin_object;		/* object pointer */
 	natural_t iin_next;		/* marequest/next in free list */
-	natural_t iin_hash;		/* hash index */
 } ipc_info_name_t;
 
 typedef ipc_info_name_t *ipc_info_name_array_t;
 
-
-typedef struct ipc_info_tree_name {
-	ipc_info_name_t iitn_name;
-	mach_port_t iitn_lchild;	/* name of left child */
-	mach_port_t iitn_rchild;	/* name of right child */
-} ipc_info_tree_name_t;
-
-typedef ipc_info_tree_name_t *ipc_info_tree_name_array_t;
-
 /*
  *	Type definitions for mach_port_kernel_object.
  *	By remarkable coincidence, these closely resemble
diff --git a/include/mach_debug/mach_debug.defs b/include/mach_debug/mach_debug.defs
index fb6e3a9..c8e8b1b 100644
--- a/include/mach_debug/mach_debug.defs
+++ b/include/mach_debug/mach_debug.defs
@@ -57,14 +57,7 @@ routine	mach_port_get_srights(
 		name		: mach_port_name_t;
 	out	srights		: mach_port_rights_t);
 
-/*
- *	Returns information about the global reverse hash table.
- */
-
-routine host_ipc_hash_info(
-		host		: host_t;
-	out	info		: hash_info_bucket_array_t,
-					CountInOut, Dealloc);
+skip;	/* host_ipc_hash_info */
 
 /*
  *	Returns information about the marequest hash table.
@@ -76,17 +69,7 @@ routine host_ipc_marequest_info(
 	out	info		: hash_info_bucket_array_t,
 					CountInOut, Dealloc);
 
-/*
- *	Returns information about an IPC space.
- */
-
-routine mach_port_space_info(
-		task		: ipc_space_t;
-	out	info		: ipc_info_space_t;
-	out	table_info	: ipc_info_name_array_t,
-					CountInOut, Dealloc;
-	out	tree_info	: ipc_info_tree_name_array_t,
-					CountInOut, Dealloc);
+skip;	/* mach_port_space_info */
 
 /*
  *	Returns information about the dead-name requests
diff --git a/include/mach_debug/mach_debug_types.defs b/include/mach_debug/mach_debug_types.defs
index d24b6f9..8df2f34 100644
--- a/include/mach_debug/mach_debug_types.defs
+++ b/include/mach_debug/mach_debug_types.defs
@@ -38,14 +38,9 @@ type cache_info_array_t = array[] of cache_info_t;
 type hash_info_bucket_t = struct[1] of natural_t;
 type hash_info_bucket_array_t = array[] of hash_info_bucket_t;
 
-type ipc_info_space_t = struct[6] of natural_t;
-
-type ipc_info_name_t = struct[9] of natural_t;
+type ipc_info_name_t = struct[6] of natural_t;
 type ipc_info_name_array_t = array[] of ipc_info_name_t;
 
-type ipc_info_tree_name_t = struct[11] of natural_t;
-type ipc_info_tree_name_array_t = array[] of ipc_info_tree_name_t;
-
 type vm_region_info_t = struct[11] of natural_t;
 type vm_region_info_array_t = array[] of vm_region_info_t;