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

diff --git a/ipc/ipc_splay.h b/ipc/ipc_splay.h
deleted file mode 100644
index 42e5a801..00000000
--- a/ipc/ipc_splay.h
+++ /dev/null
@@ -1,114 +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_splay.h
- *	Author:	Rich Draves
- *	Date:	1989
- *
- *	Declarations of primitive splay tree operations.
- */
-
-#ifndef	_IPC_IPC_SPLAY_H_
-#define _IPC_IPC_SPLAY_H_
-
-#include <mach/port.h>
-#include <kern/assert.h>
-#include <kern/macros.h>
-#include <ipc/ipc_entry.h>
-
-typedef struct ipc_splay_tree {
-	mach_port_t ist_name;		/* name used in last lookup */
-	ipc_tree_entry_t ist_root;	/* root of middle tree */
-	ipc_tree_entry_t ist_ltree;	/* root of left tree */
-	ipc_tree_entry_t *ist_ltreep;	/* pointer into left tree */
-	ipc_tree_entry_t ist_rtree;	/* root of right tree */
-	ipc_tree_entry_t *ist_rtreep;	/* pointer into right tree */
-} *ipc_splay_tree_t;
-
-#define	ist_lock(splay)		/* no locking */
-#define ist_unlock(splay)	/* no locking */
-
-/* Initialize a raw splay tree */
-extern void ipc_splay_tree_init(
-	ipc_splay_tree_t	splay);
-
-/* Pick a random entry in a splay tree */
-extern boolean_t ipc_splay_tree_pick(
-	ipc_splay_tree_t	splay,
-	mach_port_t		*namep,
-	ipc_tree_entry_t	*entryp);
-
-/* Find an entry in a splay tree */
-extern ipc_tree_entry_t ipc_splay_tree_lookup(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name);
-
-/* Insert a new entry into a splay tree */
-extern void ipc_splay_tree_insert(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry);
-
-/* Delete an entry from a splay tree */
-extern void ipc_splay_tree_delete(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_tree_entry_t	entry);
-
-/* Split a splay tree */
-extern void ipc_splay_tree_split(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	ipc_splay_tree_t	entry);
-
-/* Join two splay trees */
-extern void ipc_splay_tree_join(
-	ipc_splay_tree_t	splay,
-	ipc_splay_tree_t	small);
-
-/* Do a bounded splay tree lookup */
-extern void ipc_splay_tree_bounds(
-	ipc_splay_tree_t	splay,
-	mach_port_t		name,
-	mach_port_t		*lowerp, 
-	mach_port_t		*upperp);
-
-/* Initialize a symmetric order traversal of a splay tree */
-extern ipc_tree_entry_t ipc_splay_traverse_start(
-	ipc_splay_tree_t	splay);
-
-/* Return the next entry in a symmetric order traversal of a splay tree */
-extern ipc_tree_entry_t ipc_splay_traverse_next(
-	ipc_splay_tree_t	splay,
-	boolean_t		delete);
-
-/* Terminate a symmetric order traversal of a splay tree */
-extern void ipc_splay_traverse_finish(
-	ipc_splay_tree_t	splay);
-
-#endif	/* _IPC_IPC_SPLAY_H_ */