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, 12 insertions, 20 deletions

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