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, 17 insertions, 22 deletions

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;
 	    }