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_space.c | 104 ++++++++++---------------------------------------------- 1 file changed, 18 insertions(+), 86 deletions(-) (limited to 'ipc/ipc_space.c') diff --git a/ipc/ipc_space.c b/ipc/ipc_space.c index dcc96b3..ea3cb3b 100644 --- a/ipc/ipc_space.c +++ b/ipc/ipc_space.c @@ -46,8 +46,6 @@ #include #include #include -#include -#include #include #include #include @@ -82,6 +80,9 @@ ipc_space_release( ipc_space_release_macro(space); } +/* A place-holder object for the zeroth entry. */ +struct ipc_entry zero_entry; + /* * Routine: ipc_space_create * Purpose: @@ -102,53 +103,24 @@ ipc_space_create( ipc_space_t *spacep) { ipc_space_t space; - ipc_entry_t table; - ipc_entry_num_t new_size; - mach_port_index_t index; space = is_alloc(); if (space == IS_NULL) return KERN_RESOURCE_SHORTAGE; - table = it_entries_alloc(initial); - if (table == IE_NULL) { - is_free(space); - return KERN_RESOURCE_SHORTAGE; - } - - new_size = initial->its_size; - memset((void *) table, 0, new_size * sizeof(struct ipc_entry)); - - /* - * Initialize the free list in the table. - * Add the entries in reverse order, and - * set the generation number to -1, so that - * initial allocations produce "natural" names. - */ - - for (index = 0; index < new_size; index++) { - ipc_entry_t entry = &table[index]; - - entry->ie_bits = IE_BITS_GEN_MASK; - entry->ie_next = index+1; - } - table[new_size-1].ie_next = 0; - is_ref_lock_init(space); space->is_references = 2; is_lock_init(space); space->is_active = TRUE; - space->is_growing = FALSE; - space->is_table = table; - space->is_table_size = new_size; - space->is_table_next = initial+1; - - ipc_splay_tree_init(&space->is_tree); - space->is_tree_total = 0; - space->is_tree_small = 0; - space->is_tree_hash = 0; + + rdxtree_init(&space->is_map); rdxtree_init(&space->is_reverse_map); + /* The zeroth entry is reserved. */ + rdxtree_insert(&space->is_map, 0, &zero_entry); + space->is_size = 1; + space->is_free_list = NULL; + space->is_free_list_size = 0; *spacep = space; return KERN_SUCCESS; @@ -202,10 +174,6 @@ void ipc_space_destroy( ipc_space_t space) { - ipc_tree_entry_t tentry; - ipc_entry_t table; - ipc_entry_num_t size; - mach_port_index_t index; boolean_t active; assert(space != IS_NULL); @@ -218,60 +186,24 @@ ipc_space_destroy( if (!active) return; - /* - * If somebody is trying to grow the table, - * we must wait until they finish and figure - * out the space died. - */ + ipc_entry_t entry; + struct rdxtree_iter iter; + rdxtree_for_each(&space->is_map, &iter, entry) { + if (entry->ie_name == MACH_PORT_NULL) + continue; - is_read_lock(space); - while (space->is_growing) { - assert_wait((event_t) space, FALSE); - is_read_unlock(space); - thread_block((void (*)(void)) 0); - is_read_lock(space); - } - is_read_unlock(space); - - /* - * Now we can futz with it without having it locked. - */ - - table = space->is_table; - size = space->is_table_size; - - for (index = 0; index < size; index++) { - ipc_entry_t entry = &table[index]; mach_port_type_t type = IE_BITS_TYPE(entry->ie_bits); if (type != MACH_PORT_TYPE_NONE) { mach_port_t name = - MACH_PORT_MAKEB(index, entry->ie_bits); + MACH_PORT_MAKEB(entry->ie_name, entry->ie_bits); ipc_right_clean(space, name, entry); } - } - it_entries_free(space->is_table_next-1, table); - - for (tentry = ipc_splay_traverse_start(&space->is_tree); - tentry != ITE_NULL; - tentry = ipc_splay_traverse_next(&space->is_tree, TRUE)) { - mach_port_type_t type = IE_BITS_TYPE(tentry->ite_bits); - mach_port_t name = tentry->ite_name; - - assert(type != MACH_PORT_TYPE_NONE); - - /* use object before ipc_right_clean releases ref */ - - if (type == MACH_PORT_TYPE_SEND) - ipc_hash_global_delete(space, tentry->ite_object, - name, tentry); - - ipc_right_clean(space, name, &tentry->ite_entry); + ie_free(entry); } - ipc_splay_traverse_finish(&space->is_tree); - + rdxtree_remove_all(&space->is_map); rdxtree_remove_all(&space->is_reverse_map); /* -- cgit v1.2.3