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, 96 deletions

diff --git a/ipc/ipc_hash.h b/ipc/ipc_hash.h
deleted file mode 100644
index 929ba77..0000000
--- a/ipc/ipc_hash.h
+++ /dev/null
@@ -1,96 +0,0 @@
-/*
- * Mach Operating System
- * Copyright (c) 1991,1990,1989 Carnegie Mellon University
- * All Rights Reserved.
- *
- * Permission to use, copy, modify and distribute this software and its
- * documentation is hereby granted, provided that both the copyright
- * notice and this permission notice appear in all copies of the
- * software, derivative works or modified versions, and any portions
- * thereof, and that both notices appear in supporting documentation.
- *
- * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
- * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
- * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
- *
- * Carnegie Mellon requests users of this software to return to
- *
- *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
- *  School of Computer Science
- *  Carnegie Mellon University
- *  Pittsburgh PA 15213-3890
- *
- * any improvements or extensions that they make and grant Carnegie Mellon
- * the rights to redistribute these changes.
- */
-/*
- *	File:	ipc/ipc_hash.h
- *	Author:	Rich Draves
- *	Date:	1989
- *
- *	Declarations of entry hash table operations.
- */
-
-#ifndef	_IPC_IPC_HASH_H_
-#define _IPC_IPC_HASH_H_
-
-#include <mach/boolean.h>
-#include <mach/kern_return.h>
-
-typedef natural_t ipc_hash_index_t;
-
-extern void
-ipc_hash_init(void);
-
-#if	MACH_IPC_DEBUG
-
-extern ipc_hash_index_t
-ipc_hash_info(hash_info_bucket_t *, mach_msg_type_number_t);
-
-#endif	/* MACH_IPC_DEBUG */
-
-extern boolean_t
-ipc_hash_lookup(ipc_space_t space, ipc_object_t obj,
-		mach_port_t *namep, ipc_entry_t *entryp);
-
-extern void
-ipc_hash_insert(ipc_space_t space, ipc_object_t obj,
-		mach_port_t name, ipc_entry_t entry);
-
-extern void
-ipc_hash_delete(ipc_space_t space, ipc_object_t obj,
-		mach_port_t name, ipc_entry_t entry);
-
-/*
- *	For use by functions that know what they're doing:
- *	the global primitives, for splay tree entries,
- *	and the local primitives, for table entries.
- */
-
-#define	IPC_HASH_GLOBAL_SIZE	256
-
-extern boolean_t
-ipc_hash_global_lookup(ipc_space_t space, ipc_object_t obj,
-		       mach_port_t *namep, ipc_tree_entry_t *entryp);
-
-extern void
-ipc_hash_global_insert(ipc_space_t space, ipc_object_t obj,
-		       mach_port_t name, ipc_tree_entry_t entry);
-
-extern void
-ipc_hash_global_delete(ipc_space_t space, ipc_object_t obj,
-		       mach_port_t name, ipc_tree_entry_t entry);
-
-extern boolean_t
-ipc_hash_local_lookup(ipc_space_t space, ipc_object_t obj,
-		      mach_port_t *namep, ipc_entry_t *entryp);
-
-extern void
-ipc_hash_local_insert(ipc_space_t space, ipc_object_t obj,
-		      mach_port_index_t index, ipc_entry_t entry);
-
-extern void
-ipc_hash_local_delete(ipc_space_t space, ipc_object_t obj,
-		      mach_port_index_t index, ipc_entry_t entry);
-
-#endif	/* _IPC_IPC_HASH_H_ */