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, 0 insertions, 325 deletions

diff --git a/ipc/mach_debug.c b/ipc/mach_debug.c
index eb52e1c8..efb07a4f 100644
--- a/ipc/mach_debug.c
+++ b/ipc/mach_debug.c
@@ -46,7 +46,6 @@
 #include <vm/vm_kern.h>
 #include <ipc/ipc_space.h>
 #include <ipc/ipc_port.h>
-#include <ipc/ipc_hash.h>
 #include <ipc/ipc_marequest.h>
 #include <ipc/ipc_table.h>
 #include <ipc/ipc_right.h>
@@ -94,85 +93,6 @@ mach_port_get_srights(
 }
 
 /*
- *	Routine:	host_ipc_hash_info
- *	Purpose:
- *		Return information about the global reverse hash table.
- *	Conditions:
- *		Nothing locked.  Obeys CountInOut protocol.
- *	Returns:
- *		KERN_SUCCESS		Returned information.
- *		KERN_INVALID_HOST	The host is null.
- *		KERN_RESOURCE_SHORTAGE	Couldn't allocate memory.
- */
-
-kern_return_t
-host_ipc_hash_info(
-	host_t				host,
-	hash_info_bucket_array_t	*infop,
-	mach_msg_type_number_t 		*countp)
-{
-	vm_offset_t addr;
-	vm_size_t size = 0;	/* Suppress gcc warning */
-	hash_info_bucket_t *info;
-	unsigned int potential, actual;
-	kern_return_t kr;
-
-	if (host == HOST_NULL)
-		return KERN_INVALID_HOST;
-
-	/* start with in-line data */
-
-	info = *infop;
-	potential = *countp;
-
-	for (;;) {
-		actual = ipc_hash_info(info, potential);
-		if (actual <= potential)
-			break;
-
-		/* allocate more memory */
-
-		if (info != *infop)
-			kmem_free(ipc_kernel_map, addr, size);
-
-		size = round_page(actual * sizeof *info);
-		kr = kmem_alloc_pageable(ipc_kernel_map, &addr, size);
-		if (kr != KERN_SUCCESS)
-			return KERN_RESOURCE_SHORTAGE;
-
-		info = (hash_info_bucket_t *) addr;
-		potential = size/sizeof *info;
-	}
-
-	if (info == *infop) {
-		/* data fit in-line; nothing to deallocate */
-
-		*countp = actual;
-	} else if (actual == 0) {
-		kmem_free(ipc_kernel_map, addr, size);
-
-		*countp = 0;
-	} else {
-		vm_map_copy_t copy;
-		vm_size_t used;
-
-		used = round_page(actual * sizeof *info);
-
-		if (used != size)
-			kmem_free(ipc_kernel_map, addr + used, size - used);
-
-		kr = vm_map_copyin(ipc_kernel_map, addr, used,
-				   TRUE, &copy);
-		assert(kr == KERN_SUCCESS);
-
-		*infop = (hash_info_bucket_t *) copy;
-		*countp = actual;
-	}
-
-	return KERN_SUCCESS;
-}
-
-/*
  *	Routine:	host_ipc_marequest_info
  *	Purpose:
  *		Return information about the marequest hash table.
@@ -253,251 +173,6 @@ host_ipc_marequest_info(
 }
 
 /*
- *	Routine:	mach_port_space_info
- *	Purpose:
- *		Returns information about an IPC space.
- *	Conditions:
- *		Nothing locked.  Obeys CountInOut protocol.
- *	Returns:
- *		KERN_SUCCESS		Returned information.
- *		KERN_INVALID_TASK	The space is null.
- *		KERN_INVALID_TASK	The space is dead.
- *		KERN_RESOURCE_SHORTAGE	Couldn't allocate memory.
- */
-
-kern_return_t
-mach_port_space_info(
-	ipc_space_t			space,
-	ipc_info_space_t		*infop,
-	ipc_info_name_array_t		*tablep,
-	mach_msg_type_number_t 		*tableCntp,
-	ipc_info_tree_name_array_t	*treep,
-	mach_msg_type_number_t 		*treeCntp)
-{
-	ipc_info_name_t *table_info;
-	unsigned int table_potential, table_actual;
-	vm_offset_t table_addr;
-	vm_size_t table_size = 0;	/* Suppress gcc warning */
-	ipc_info_tree_name_t *tree_info;
-	unsigned int tree_potential, tree_actual;
-	vm_offset_t tree_addr;
-	vm_size_t tree_size = 0;	/* Suppress gcc warning */
-	ipc_tree_entry_t tentry;
-	ipc_entry_t table;
-	ipc_entry_num_t tsize;
-	mach_port_index_t index;
-	kern_return_t kr;
-
-	if (space == IS_NULL)
-		return KERN_INVALID_TASK;
-
-	/* start with in-line memory */
-
-	table_info = *tablep;
-	table_potential = *tableCntp;
-	tree_info = *treep;
-	tree_potential = *treeCntp;
-
-	for (;;) {
-		is_read_lock(space);
-		if (!space->is_active) {
-			is_read_unlock(space);
-			if (table_info != *tablep)
-				kmem_free(ipc_kernel_map,
-					  table_addr, table_size);
-			if (tree_info != *treep)
-				kmem_free(ipc_kernel_map,
-					  tree_addr, tree_size);
-			return KERN_INVALID_TASK;
-		}
-
-		table_actual = space->is_table_size;
-		tree_actual = space->is_tree_total;
-
-		if ((table_actual <= table_potential) &&
-		    (tree_actual <= tree_potential))
-			break;
-
-		is_read_unlock(space);
-
-		if (table_actual > table_potential) {
-			if (table_info != *tablep)
-				kmem_free(ipc_kernel_map,
-					  table_addr, table_size);
-
-			table_size = round_page(table_actual *
-						sizeof *table_info);
-			kr = kmem_alloc(ipc_kernel_map,
-					&table_addr, table_size);
-			if (kr != KERN_SUCCESS) {
-				if (tree_info != *treep)
-					kmem_free(ipc_kernel_map,
-						  tree_addr, tree_size);
-
-				return KERN_RESOURCE_SHORTAGE;
-			}
-
-			table_info = (ipc_info_name_t *) table_addr;
-			table_potential = table_size/sizeof *table_info;
-		}
-
-		if (tree_actual > tree_potential) {
-			if (tree_info != *treep)
-				kmem_free(ipc_kernel_map,
-					  tree_addr, tree_size);
-
-			tree_size = round_page(tree_actual *
-					       sizeof *tree_info);
-			kr = kmem_alloc(ipc_kernel_map,
-					&tree_addr, tree_size);
-			if (kr != KERN_SUCCESS) {
-				if (table_info != *tablep)
-					kmem_free(ipc_kernel_map,
-						  table_addr, table_size);
-
-				return KERN_RESOURCE_SHORTAGE;
-			}
-
-			tree_info = (ipc_info_tree_name_t *) tree_addr;
-			tree_potential = tree_size/sizeof *tree_info;
-		}
-	}
-	/* space is read-locked and active; we have enough wired memory */
-
-	infop->iis_genno_mask = MACH_PORT_NGEN(MACH_PORT_DEAD);
-	infop->iis_table_size = space->is_table_size;
-	infop->iis_table_next = space->is_table_next->its_size;
-	infop->iis_tree_size = space->is_tree_total;
-	infop->iis_tree_small = space->is_tree_small;
-	infop->iis_tree_hash = space->is_tree_hash;
-
-	table = space->is_table;
-	tsize = space->is_table_size;
-
-	for (index = 0; index < tsize; index++) {
-		ipc_info_name_t *iin = &table_info[index];
-		ipc_entry_t entry = &table[index];
-		ipc_entry_bits_t bits = entry->ie_bits;
-
-		iin->iin_name = MACH_PORT_MAKEB(index, bits);
-		iin->iin_collision = (bits & IE_BITS_COLLISION) ? TRUE : FALSE;
-		iin->iin_compat = FALSE;
-		iin->iin_marequest = (bits & IE_BITS_MAREQUEST) ? TRUE : FALSE;
-		iin->iin_type = IE_BITS_TYPE(bits);
-		iin->iin_urefs = IE_BITS_UREFS(bits);
-		iin->iin_object = (vm_offset_t) entry->ie_object;
-		iin->iin_next = entry->ie_next;
-		iin->iin_hash = entry->ie_index;
-	}
-
-	for (tentry = ipc_splay_traverse_start(&space->is_tree), index = 0;
-	     tentry != ITE_NULL;
-	     tentry = ipc_splay_traverse_next(&space->is_tree, FALSE)) {
-		ipc_info_tree_name_t *iitn = &tree_info[index++];
-		ipc_info_name_t *iin = &iitn->iitn_name;
-		ipc_entry_t entry = &tentry->ite_entry;
-		ipc_entry_bits_t bits = entry->ie_bits;
-
-		assert(IE_BITS_TYPE(bits) != MACH_PORT_TYPE_NONE);
-
-		iin->iin_name = tentry->ite_name;
-		iin->iin_collision = (bits & IE_BITS_COLLISION) ? TRUE : FALSE;
-		iin->iin_compat = FALSE;
-		iin->iin_marequest = (bits & IE_BITS_MAREQUEST) ? TRUE : FALSE;
-		iin->iin_type = IE_BITS_TYPE(bits);
-		iin->iin_urefs = IE_BITS_UREFS(bits);
-		iin->iin_object = (vm_offset_t) entry->ie_object;
-		iin->iin_next = entry->ie_next;
-		iin->iin_hash = entry->ie_index;
-
-		if (tentry->ite_lchild == ITE_NULL)
-			iitn->iitn_lchild = MACH_PORT_NULL;
-		else
-			iitn->iitn_lchild = tentry->ite_lchild->ite_name;
-
-		if (tentry->ite_rchild == ITE_NULL)
-			iitn->iitn_rchild = MACH_PORT_NULL;
-		else
-			iitn->iitn_rchild = tentry->ite_rchild->ite_name;
-
-	}
-	ipc_splay_traverse_finish(&space->is_tree);
-	is_read_unlock(space);
-
-	if (table_info == *tablep) {
-		/* data fit in-line; nothing to deallocate */
-
-		*tableCntp = table_actual;
-	} else if (table_actual == 0) {
-		kmem_free(ipc_kernel_map, table_addr, table_size);
-
-		*tableCntp = 0;
-	} else {
-		vm_size_t size_used, rsize_used;
-		vm_map_copy_t copy;
-
-		/* kmem_alloc doesn't zero memory */
-
-		size_used = table_actual * sizeof *table_info;
-		rsize_used = round_page(size_used);
-
-		if (rsize_used != table_size)
-			kmem_free(ipc_kernel_map,
-				  table_addr + rsize_used,
-				  table_size - rsize_used);
-
-		if (size_used != rsize_used)
-			memset((void *) (table_addr + size_used), 0,
-			      rsize_used - size_used);
-
-		kr = vm_map_copyin(ipc_kernel_map, table_addr, rsize_used,
-				   TRUE, &copy);
-
-		assert(kr == KERN_SUCCESS);
-
-		*tablep = (ipc_info_name_t *) copy;
-		*tableCntp = table_actual;
-	}
-
-	if (tree_info == *treep) {
-		/* data fit in-line; nothing to deallocate */
-
-		*treeCntp = tree_actual;
-	} else if (tree_actual == 0) {
-		kmem_free(ipc_kernel_map, tree_addr, tree_size);
-
-		*treeCntp = 0;
-	} else {
-		vm_size_t size_used, rsize_used;
-		vm_map_copy_t copy;
-
-		/* kmem_alloc doesn't zero memory */
-
-		size_used = tree_actual * sizeof *tree_info;
-		rsize_used = round_page(size_used);
-
-		if (rsize_used != tree_size)
-			kmem_free(ipc_kernel_map,
-				  tree_addr + rsize_used,
-				  tree_size - rsize_used);
-
-		if (size_used != rsize_used)
-			memset((void *) (tree_addr + size_used), 0,
-			      rsize_used - size_used);
-
-		kr = vm_map_copyin(ipc_kernel_map, tree_addr, rsize_used,
-				   TRUE, &copy);
-
-		assert(kr == KERN_SUCCESS);
-
-		*treep = (ipc_info_tree_name_t *) copy;
-		*treeCntp = tree_actual;
-	}
-
-	return KERN_SUCCESS;
-}
-
-/*
  *	Routine:	mach_port_dnrequest_info
  *	Purpose:
  *		Returns information about the dead-name requests