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/mach_debug.c | 325 ------------------------------------------------------- 1 file changed, 325 deletions(-) (limited to 'ipc/mach_debug.c') diff --git a/ipc/mach_debug.c b/ipc/mach_debug.c index eb52e1c..efb07a4 100644 --- a/ipc/mach_debug.c +++ b/ipc/mach_debug.c @@ -46,7 +46,6 @@ #include #include #include -#include #include #include #include @@ -93,85 +92,6 @@ mach_port_get_srights( return KERN_SUCCESS; } -/* - * Routine: host_ipc_hash_info - * Purpose: - * Return information about the global reverse hash table. - * Conditions: - * Nothing locked. Obeys CountInOut protocol. - * Returns: - * KERN_SUCCESS Returned information. - * KERN_INVALID_HOST The host is null. - * KERN_RESOURCE_SHORTAGE Couldn't allocate memory. - */ - -kern_return_t -host_ipc_hash_info( - host_t host, - hash_info_bucket_array_t *infop, - mach_msg_type_number_t *countp) -{ - vm_offset_t addr; - vm_size_t size = 0; /* Suppress gcc warning */ - hash_info_bucket_t *info; - unsigned int potential, actual; - kern_return_t kr; - - if (host == HOST_NULL) - return KERN_INVALID_HOST; - - /* start with in-line data */ - - info = *infop; - potential = *countp; - - for (;;) { - actual = ipc_hash_info(info, potential); - if (actual <= potential) - break; - - /* allocate more memory */ - - if (info != *infop) - kmem_free(ipc_kernel_map, addr, size); - - size = round_page(actual * sizeof *info); - kr = kmem_alloc_pageable(ipc_kernel_map, &addr, size); - if (kr != KERN_SUCCESS) - return KERN_RESOURCE_SHORTAGE; - - info = (hash_info_bucket_t *) addr; - potential = size/sizeof *info; - } - - if (info == *infop) { - /* data fit in-line; nothing to deallocate */ - - *countp = actual; - } else if (actual == 0) { - kmem_free(ipc_kernel_map, addr, size); - - *countp = 0; - } else { - vm_map_copy_t copy; - vm_size_t used; - - used = round_page(actual * sizeof *info); - - if (used != size) - kmem_free(ipc_kernel_map, addr + used, size - used); - - kr = vm_map_copyin(ipc_kernel_map, addr, used, - TRUE, ©); - assert(kr == KERN_SUCCESS); - - *infop = (hash_info_bucket_t *) copy; - *countp = actual; - } - - return KERN_SUCCESS; -} - /* * Routine: host_ipc_marequest_info * Purpose: @@ -252,251 +172,6 @@ host_ipc_marequest_info( return KERN_SUCCESS; } -/* - * Routine: mach_port_space_info - * Purpose: - * Returns information about an IPC space. - * Conditions: - * Nothing locked. Obeys CountInOut protocol. - * Returns: - * KERN_SUCCESS Returned information. - * KERN_INVALID_TASK The space is null. - * KERN_INVALID_TASK The space is dead. - * KERN_RESOURCE_SHORTAGE Couldn't allocate memory. - */ - -kern_return_t -mach_port_space_info( - ipc_space_t space, - ipc_info_space_t *infop, - ipc_info_name_array_t *tablep, - mach_msg_type_number_t *tableCntp, - ipc_info_tree_name_array_t *treep, - mach_msg_type_number_t *treeCntp) -{ - ipc_info_name_t *table_info; - unsigned int table_potential, table_actual; - vm_offset_t table_addr; - vm_size_t table_size = 0; /* Suppress gcc warning */ - ipc_info_tree_name_t *tree_info; - unsigned int tree_potential, tree_actual; - vm_offset_t tree_addr; - vm_size_t tree_size = 0; /* Suppress gcc warning */ - ipc_tree_entry_t tentry; - ipc_entry_t table; - ipc_entry_num_t tsize; - mach_port_index_t index; - kern_return_t kr; - - if (space == IS_NULL) - return KERN_INVALID_TASK; - - /* start with in-line memory */ - - table_info = *tablep; - table_potential = *tableCntp; - tree_info = *treep; - tree_potential = *treeCntp; - - for (;;) { - is_read_lock(space); - if (!space->is_active) { - is_read_unlock(space); - if (table_info != *tablep) - kmem_free(ipc_kernel_map, - table_addr, table_size); - if (tree_info != *treep) - kmem_free(ipc_kernel_map, - tree_addr, tree_size); - return KERN_INVALID_TASK; - } - - table_actual = space->is_table_size; - tree_actual = space->is_tree_total; - - if ((table_actual <= table_potential) && - (tree_actual <= tree_potential)) - break; - - is_read_unlock(space); - - if (table_actual > table_potential) { - if (table_info != *tablep) - kmem_free(ipc_kernel_map, - table_addr, table_size); - - table_size = round_page(table_actual * - sizeof *table_info); - kr = kmem_alloc(ipc_kernel_map, - &table_addr, table_size); - if (kr != KERN_SUCCESS) { - if (tree_info != *treep) - kmem_free(ipc_kernel_map, - tree_addr, tree_size); - - return KERN_RESOURCE_SHORTAGE; - } - - table_info = (ipc_info_name_t *) table_addr; - table_potential = table_size/sizeof *table_info; - } - - if (tree_actual > tree_potential) { - if (tree_info != *treep) - kmem_free(ipc_kernel_map, - tree_addr, tree_size); - - tree_size = round_page(tree_actual * - sizeof *tree_info); - kr = kmem_alloc(ipc_kernel_map, - &tree_addr, tree_size); - if (kr != KERN_SUCCESS) { - if (table_info != *tablep) - kmem_free(ipc_kernel_map, - table_addr, table_size); - - return KERN_RESOURCE_SHORTAGE; - } - - tree_info = (ipc_info_tree_name_t *) tree_addr; - tree_potential = tree_size/sizeof *tree_info; - } - } - /* space is read-locked and active; we have enough wired memory */ - - infop->iis_genno_mask = MACH_PORT_NGEN(MACH_PORT_DEAD); - infop->iis_table_size = space->is_table_size; - infop->iis_table_next = space->is_table_next->its_size; - infop->iis_tree_size = space->is_tree_total; - infop->iis_tree_small = space->is_tree_small; - infop->iis_tree_hash = space->is_tree_hash; - - table = space->is_table; - tsize = space->is_table_size; - - for (index = 0; index < tsize; index++) { - ipc_info_name_t *iin = &table_info[index]; - ipc_entry_t entry = &table[index]; - ipc_entry_bits_t bits = entry->ie_bits; - - iin->iin_name = MACH_PORT_MAKEB(index, bits); - iin->iin_collision = (bits & IE_BITS_COLLISION) ? TRUE : FALSE; - iin->iin_compat = FALSE; - iin->iin_marequest = (bits & IE_BITS_MAREQUEST) ? TRUE : FALSE; - iin->iin_type = IE_BITS_TYPE(bits); - iin->iin_urefs = IE_BITS_UREFS(bits); - iin->iin_object = (vm_offset_t) entry->ie_object; - iin->iin_next = entry->ie_next; - iin->iin_hash = entry->ie_index; - } - - for (tentry = ipc_splay_traverse_start(&space->is_tree), index = 0; - tentry != ITE_NULL; - tentry = ipc_splay_traverse_next(&space->is_tree, FALSE)) { - ipc_info_tree_name_t *iitn = &tree_info[index++]; - ipc_info_name_t *iin = &iitn->iitn_name; - ipc_entry_t entry = &tentry->ite_entry; - ipc_entry_bits_t bits = entry->ie_bits; - - assert(IE_BITS_TYPE(bits) != MACH_PORT_TYPE_NONE); - - iin->iin_name = tentry->ite_name; - iin->iin_collision = (bits & IE_BITS_COLLISION) ? TRUE : FALSE; - iin->iin_compat = FALSE; - iin->iin_marequest = (bits & IE_BITS_MAREQUEST) ? TRUE : FALSE; - iin->iin_type = IE_BITS_TYPE(bits); - iin->iin_urefs = IE_BITS_UREFS(bits); - iin->iin_object = (vm_offset_t) entry->ie_object; - iin->iin_next = entry->ie_next; - iin->iin_hash = entry->ie_index; - - if (tentry->ite_lchild == ITE_NULL) - iitn->iitn_lchild = MACH_PORT_NULL; - else - iitn->iitn_lchild = tentry->ite_lchild->ite_name; - - if (tentry->ite_rchild == ITE_NULL) - iitn->iitn_rchild = MACH_PORT_NULL; - else - iitn->iitn_rchild = tentry->ite_rchild->ite_name; - - } - ipc_splay_traverse_finish(&space->is_tree); - is_read_unlock(space); - - if (table_info == *tablep) { - /* data fit in-line; nothing to deallocate */ - - *tableCntp = table_actual; - } else if (table_actual == 0) { - kmem_free(ipc_kernel_map, table_addr, table_size); - - *tableCntp = 0; - } else { - vm_size_t size_used, rsize_used; - vm_map_copy_t copy; - - /* kmem_alloc doesn't zero memory */ - - size_used = table_actual * sizeof *table_info; - rsize_used = round_page(size_used); - - if (rsize_used != table_size) - kmem_free(ipc_kernel_map, - table_addr + rsize_used, - table_size - rsize_used); - - if (size_used != rsize_used) - memset((void *) (table_addr + size_used), 0, - rsize_used - size_used); - - kr = vm_map_copyin(ipc_kernel_map, table_addr, rsize_used, - TRUE, ©); - - assert(kr == KERN_SUCCESS); - - *tablep = (ipc_info_name_t *) copy; - *tableCntp = table_actual; - } - - if (tree_info == *treep) { - /* data fit in-line; nothing to deallocate */ - - *treeCntp = tree_actual; - } else if (tree_actual == 0) { - kmem_free(ipc_kernel_map, tree_addr, tree_size); - - *treeCntp = 0; - } else { - vm_size_t size_used, rsize_used; - vm_map_copy_t copy; - - /* kmem_alloc doesn't zero memory */ - - size_used = tree_actual * sizeof *tree_info; - rsize_used = round_page(size_used); - - if (rsize_used != tree_size) - kmem_free(ipc_kernel_map, - tree_addr + rsize_used, - tree_size - rsize_used); - - if (size_used != rsize_used) - memset((void *) (tree_addr + size_used), 0, - rsize_used - size_used); - - kr = vm_map_copyin(ipc_kernel_map, tree_addr, rsize_used, - TRUE, ©); - - assert(kr == KERN_SUCCESS); - - *treep = (ipc_info_tree_name_t *) copy; - *treeCntp = tree_actual; - } - - return KERN_SUCCESS; -} - /* * Routine: mach_port_dnrequest_info * Purpose: -- cgit v1.2.3