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, 9 insertions, 46 deletions

diff --git a/ipc/ipc_entry.h b/ipc/ipc_entry.h
index 0caa70b0..5c1f8fd4 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,