ipc: replace reverse hash table with a radix tree

Currently, there is a hash table mapping (space, object) tuples to
`ipc_entry' objects.  This hash table is intertwined with the IPC
tables.  There is one hash table per IPC space, but it is only for the
entries in the IPC table.  This hash table is called `local' in the
source.  All IPC entries being spilled into the splay tree are instead
mapped by a global hash table.

Replace the local (i.e. per IPC space) reverse hash table with a radix
tree.

* ipc/ipc_entry.c (ipc_entry_grow_table): Adjust accordingly.
* ipc/ipc_entry.h (struct ipc_entry): Adjust comment.
* ipc/ipc_hash.c: Adjust comment explaining the local lookup table.
(IPC_LOCAL_HASH_INVARIANT): New macro.
(ipc_hash_local_lookup): Use the new `ipc_reverse_lookup' function.
(ipc_hash_local_insert): Use the new `ipc_reverse_insert' function.
(ipc_hash_local_delete): Use the new `ipc_reverse_remove' function.
* ipc/ipc_space.c (ipc_space_create): Initialize radix tree.
(ipc_space_destroy): Free radix tree.
* ipc/ipc_space.h (struct ipc_space): Add radix tree.
(ipc_reverse_insert): New function.
(ipc_reverse_remove): Likewise.
(ipc_reverse_remove_all): Likewise.
(ipc_reverse_lookup): Likewise.
* ipc/ipc_right.c (ipc_right_clean): Update comment.

1 files changed, 63 insertions, 0 deletions

diff --git a/ipc/ipc_space.h b/ipc/ipc_space.h
index 3bd2f4d0..f41c64c2 100644
--- a/ipc/ipc_space.h
+++ b/ipc/ipc_space.h
@@ -42,8 +42,10 @@
 #include <mach/boolean.h>
 #include <mach/kern_return.h>
 #include <mach/mach_types.h>
+#include <machine/vm_param.h>
 #include <kern/macros.h>
 #include <kern/lock.h>
+#include <kern/rdxtree.h>
 #include <kern/slab.h>
 #include <ipc/ipc_splay.h>
 #include <ipc/ipc_types.h>
@@ -79,6 +81,8 @@ struct ipc_space {
 	ipc_entry_num_t is_tree_total;	/* number of entries in the tree */
 	ipc_entry_num_t is_tree_small;	/* # of small entries in the tree */
 	ipc_entry_num_t is_tree_hash;	/* # of hashed entries in the tree */
+	struct rdxtree is_reverse_map;	/* maps objects to entries */
+
 };
 
 #define	IS_NULL			((ipc_space_t) 0)
@@ -135,4 +139,63 @@ kern_return_t	ipc_space_create(ipc_table_size_t, ipc_space_t *);
 kern_return_t	ipc_space_create_special(struct ipc_space **);
 void		ipc_space_destroy(struct ipc_space *);
 
+/* Reverse lookups.  */
+
+/* Cast a pointer to a suitable key.  */
+#define KEY(X)								\
+	({								\
+		assert((((unsigned long) (X)) & 0x07) == 0);		\
+		((unsigned long long)					\
+		 (((unsigned long) (X) - VM_MIN_KERNEL_ADDRESS) >> 3));	\
+	})
+
+/* Insert (OBJ, ENTRY) pair into the reverse mapping.  SPACE must
+   be write-locked.  */
+static inline kern_return_t
+ipc_reverse_insert(ipc_space_t space,
+		   ipc_object_t obj,
+		   ipc_entry_t entry)
+{
+	assert(space != IS_NULL);
+	assert(obj != IO_NULL);
+	return (kern_return_t) rdxtree_insert(&space->is_reverse_map,
+					      KEY(obj), entry);
+}
+
+/* Remove OBJ from the reverse mapping.  SPACE must be
+   write-locked.  */
+static inline ipc_entry_t
+ipc_reverse_remove(ipc_space_t space,
+		   ipc_object_t obj)
+{
+	assert(space != IS_NULL);
+	assert(obj != IO_NULL);
+	return rdxtree_remove(&space->is_reverse_map, KEY(obj));
+}
+
+/* Remove all entries from the reverse mapping.  SPACE must be
+   write-locked.  */
+static inline void
+ipc_reverse_remove_all(ipc_space_t space)
+{
+	assert(space != IS_NULL);
+	rdxtree_remove_all(&space->is_reverse_map);
+	assert(space->is_reverse_map.height == 0);
+	assert(space->is_reverse_map.root == NULL);
+}
+
+/* Return ENTRY related to OBJ, or NULL if no such entry is found in
+   the reverse mapping.  SPACE must be read-locked or
+   write-locked.  */
+static inline ipc_entry_t
+ipc_reverse_lookup(ipc_space_t space,
+		   ipc_object_t obj)
+{
+	assert(space != IS_NULL);
+	assert(obj != IO_NULL);
+	return rdxtree_lookup(&space->is_reverse_map, KEY(obj));
+}
+
+#undef KEY
+
 #endif	/* _IPC_IPC_SPACE_H_ */