From 77b3b60aaee2382142dc7ed50e5b36664cdb21bc Mon Sep 17 00:00:00 2001
From: Justus Winter <4winter@informatik.uni-hamburg.de>
Date: Fri, 20 Mar 2015 00:21:14 +0100
Subject: 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.
---
ipc/ipc_entry.h | 55 +++++++++----------------------------------------------
1 file changed, 9 insertions(+), 46 deletions(-)
(limited to 'ipc/ipc_entry.h')
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,
--
cgit v1.2.3