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_right.c | 39 +++++++++++++++++---------------------- 1 file changed, 17 insertions(+), 22 deletions(-) (limited to 'ipc/ipc_right.c') diff --git a/ipc/ipc_right.c b/ipc/ipc_right.c index 35061c9a..773b3b10 100644 --- a/ipc/ipc_right.c +++ b/ipc/ipc_right.c @@ -43,7 +43,6 @@ #include #include #include -#include #include #include #include @@ -142,7 +141,8 @@ ipc_right_reverse( return TRUE; } - if (ipc_hash_lookup(space, (ipc_object_t) port, namep, entryp)) { + if ((*entryp = ipc_reverse_lookup(space, (ipc_object_t) port))) { + *namep = (*entryp)->ie_name; assert((entry = *entryp) != IE_NULL); assert(IE_BITS_TYPE(entry->ie_bits) == MACH_PORT_TYPE_SEND); assert(port == (ipc_port_t) entry->ie_object); @@ -392,7 +392,7 @@ ipc_right_check( ipc_marequest_cancel(space, name); } - ipc_hash_delete(space, (ipc_object_t) port, name, entry); + ipc_reverse_remove(space, (ipc_object_t) port); } else { assert(IE_BITS_TYPE(bits) == MACH_PORT_TYPE_SEND_ONCE); assert(IE_BITS_UREFS(bits) == 1); @@ -609,8 +609,7 @@ ipc_right_destroy( } if (type == MACH_PORT_TYPE_SEND) - ipc_hash_delete(space, (ipc_object_t) port, - name, entry); + ipc_reverse_remove(space, (ipc_object_t) port); ip_lock(port); @@ -789,8 +788,7 @@ ipc_right_dealloc( dnrequest = ipc_right_dncancel_macro(space, port, name, entry); - ipc_hash_delete(space, (ipc_object_t) port, - name, entry); + ipc_reverse_remove(space, (ipc_object_t) port); if (bits & IE_BITS_MAREQUEST) ipc_marequest_cancel(space, name); @@ -1134,8 +1132,7 @@ ipc_right_delta( dnrequest = ipc_right_dncancel_macro( space, port, name, entry); - ipc_hash_delete(space, (ipc_object_t) port, - name, entry); + ipc_reverse_remove(space, (ipc_object_t) port); if (bits & IE_BITS_MAREQUEST) ipc_marequest_cancel(space, name); @@ -1410,8 +1407,8 @@ ipc_right_copyin( assert(IE_BITS_UREFS(bits) > 0); assert(port->ip_srights > 0); - ipc_hash_insert(space, (ipc_object_t) port, - name, entry); + entry->ie_name = name; + ipc_reverse_insert(space, (ipc_object_t) port, entry); ip_reference(port); } else { @@ -1534,8 +1531,7 @@ ipc_right_copyin( dnrequest = ipc_right_dncancel_macro( space, port, name, entry); - ipc_hash_delete(space, (ipc_object_t) port, - name, entry); + ipc_reverse_remove(space, (ipc_object_t) port); if (bits & IE_BITS_MAREQUEST) ipc_marequest_cancel(space, name); @@ -1796,8 +1792,7 @@ ipc_right_copyin_two( dnrequest = ipc_right_dncancel_macro(space, port, name, entry); - ipc_hash_delete(space, (ipc_object_t) port, - name, entry); + ipc_reverse_remove(space, (ipc_object_t) port); if (bits & IE_BITS_MAREQUEST) ipc_marequest_cancel(space, name); @@ -1921,8 +1916,8 @@ ipc_right_copyout( /* entry is locked holding ref, so can use port */ - ipc_hash_insert(space, (ipc_object_t) port, - name, entry); + entry->ie_name = name; + ipc_reverse_insert(space, (ipc_object_t) port, entry); } entry->ie_bits = (bits | MACH_PORT_TYPE_SEND) + 1; @@ -1956,8 +1951,7 @@ ipc_right_copyout( /* entry is locked holding ref, so can use port */ - ipc_hash_delete(space, (ipc_object_t) port, - name, entry); + ipc_reverse_remove(space, (ipc_object_t) port); } else { assert(IE_BITS_TYPE(bits) == MACH_PORT_TYPE_NONE); assert(IE_BITS_UREFS(bits) == 0); @@ -2083,7 +2077,7 @@ ipc_right_rename( ipc_marequest_rename(space, oname, nname); } - /* initialize nentry before letting ipc_hash_insert see it */ + /* initialize nentry before letting ipc_reverse_insert see it */ assert((nentry->ie_bits & IE_BITS_RIGHT_MASK) == 0); nentry->ie_bits |= bits & IE_BITS_RIGHT_MASK; @@ -2097,8 +2091,9 @@ ipc_right_rename( port = (ipc_port_t) object; assert(port != IP_NULL); - ipc_hash_delete(space, (ipc_object_t) port, oname, oentry); - ipc_hash_insert(space, (ipc_object_t) port, nname, nentry); + ipc_reverse_remove(space, (ipc_object_t) port); + nentry->ie_name = nname; + ipc_reverse_insert(space, (ipc_object_t) port, nentry); break; } -- cgit v1.2.3