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. --- include/mach_debug/ipc_info.h | 23 ----------------------- include/mach_debug/mach_debug.defs | 21 ++------------------- include/mach_debug/mach_debug_types.defs | 7 +------ 3 files changed, 3 insertions(+), 48 deletions(-) (limited to 'include') diff --git a/include/mach_debug/ipc_info.h b/include/mach_debug/ipc_info.h index ef0b0c6..a47ae7b 100644 --- a/include/mach_debug/ipc_info.h +++ b/include/mach_debug/ipc_info.h @@ -43,40 +43,17 @@ * in mach_debug_types.defs when adding/removing fields. */ - -typedef struct ipc_info_space { - natural_t iis_genno_mask; /* generation number mask */ - natural_t iis_table_size; /* size of table */ - natural_t iis_table_next; /* next possible size of table */ - natural_t iis_tree_size; /* size of tree */ - natural_t iis_tree_small; /* # of small entries in tree */ - natural_t iis_tree_hash; /* # of hashed entries in tree */ -} ipc_info_space_t; - - typedef struct ipc_info_name { mach_port_t iin_name; /* port name, including gen number */ -/*boolean_t*/integer_t iin_collision; /* collision at this entry? */ -/*boolean_t*/integer_t iin_compat; /* is this a compat-mode entry? */ /*boolean_t*/integer_t iin_marequest; /* extant msg-accepted request? */ mach_port_type_t iin_type; /* straight port type */ mach_port_urefs_t iin_urefs; /* user-references */ vm_offset_t iin_object; /* object pointer */ natural_t iin_next; /* marequest/next in free list */ - natural_t iin_hash; /* hash index */ } ipc_info_name_t; typedef ipc_info_name_t *ipc_info_name_array_t; - -typedef struct ipc_info_tree_name { - ipc_info_name_t iitn_name; - mach_port_t iitn_lchild; /* name of left child */ - mach_port_t iitn_rchild; /* name of right child */ -} ipc_info_tree_name_t; - -typedef ipc_info_tree_name_t *ipc_info_tree_name_array_t; - /* * Type definitions for mach_port_kernel_object. * By remarkable coincidence, these closely resemble diff --git a/include/mach_debug/mach_debug.defs b/include/mach_debug/mach_debug.defs index fb6e3a9..c8e8b1b 100644 --- a/include/mach_debug/mach_debug.defs +++ b/include/mach_debug/mach_debug.defs @@ -57,14 +57,7 @@ routine mach_port_get_srights( name : mach_port_name_t; out srights : mach_port_rights_t); -/* - * Returns information about the global reverse hash table. - */ - -routine host_ipc_hash_info( - host : host_t; - out info : hash_info_bucket_array_t, - CountInOut, Dealloc); +skip; /* host_ipc_hash_info */ /* * Returns information about the marequest hash table. @@ -76,17 +69,7 @@ routine host_ipc_marequest_info( out info : hash_info_bucket_array_t, CountInOut, Dealloc); -/* - * Returns information about an IPC space. - */ - -routine mach_port_space_info( - task : ipc_space_t; - out info : ipc_info_space_t; - out table_info : ipc_info_name_array_t, - CountInOut, Dealloc; - out tree_info : ipc_info_tree_name_array_t, - CountInOut, Dealloc); +skip; /* mach_port_space_info */ /* * Returns information about the dead-name requests diff --git a/include/mach_debug/mach_debug_types.defs b/include/mach_debug/mach_debug_types.defs index d24b6f9..8df2f34 100644 --- a/include/mach_debug/mach_debug_types.defs +++ b/include/mach_debug/mach_debug_types.defs @@ -38,14 +38,9 @@ type cache_info_array_t = array[] of cache_info_t; type hash_info_bucket_t = struct[1] of natural_t; type hash_info_bucket_array_t = array[] of hash_info_bucket_t; -type ipc_info_space_t = struct[6] of natural_t; - -type ipc_info_name_t = struct[9] of natural_t; +type ipc_info_name_t = struct[6] of natural_t; type ipc_info_name_array_t = array[] of ipc_info_name_t; -type ipc_info_tree_name_t = struct[11] of natural_t; -type ipc_info_tree_name_array_t = array[] of ipc_info_tree_name_t; - type vm_region_info_t = struct[11] of natural_t; type vm_region_info_array_t = array[] of vm_region_info_t; -- cgit v1.2.3