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_port.c | 60 +++++++++------------------------------------------------ 1 file changed, 9 insertions(+), 51 deletions(-) (limited to 'ipc/mach_port.c') diff --git a/ipc/mach_port.c b/ipc/mach_port.c index 4e895275..93a1248f 100644 --- a/ipc/mach_port.c +++ b/ipc/mach_port.c @@ -150,10 +150,6 @@ mach_port_names( mach_port_type_t **typesp, mach_msg_type_number_t *typesCnt) { - ipc_tree_entry_t tentry; - ipc_entry_t table; - ipc_entry_num_t tsize; - mach_port_index_t index; ipc_entry_num_t actual; /* this many names */ ipc_port_timestamp_t timestamp; /* logical time of this operation */ mach_port_t *names; @@ -190,7 +186,7 @@ mach_port_names( /* upper bound on number of names in the space */ - bound = space->is_table_size + space->is_tree_total; + bound = space->is_size; size_needed = round_page(bound * sizeof(mach_port_t)); if (size_needed <= size) @@ -235,33 +231,16 @@ mach_port_names( timestamp = ipc_port_timestamp(); - table = space->is_table; - tsize = space->is_table_size; - - for (index = 0; index < tsize; index++) { - ipc_entry_t entry = &table[index]; + ipc_entry_t entry; + struct rdxtree_iter iter; + rdxtree_for_each(&space->is_map, &iter, entry) { ipc_entry_bits_t bits = entry->ie_bits; if (IE_BITS_TYPE(bits) != MACH_PORT_TYPE_NONE) { - mach_port_t name = MACH_PORT_MAKEB(index, bits); - - mach_port_names_helper(timestamp, entry, name, + mach_port_names_helper(timestamp, entry, entry->ie_name, names, types, &actual); } } - - for (tentry = ipc_splay_traverse_start(&space->is_tree); - tentry != ITE_NULL; - tentry = ipc_splay_traverse_next(&space->is_tree, FALSE)) { - ipc_entry_t entry = &tentry->ite_entry; - mach_port_t name = tentry->ite_name; - - assert(IE_BITS_TYPE(tentry->ite_bits) != MACH_PORT_TYPE_NONE); - - mach_port_names_helper(timestamp, entry, name, - names, types, &actual); - } - ipc_splay_traverse_finish(&space->is_tree); is_read_unlock(space); if (actual == 0) { @@ -946,10 +925,7 @@ mach_port_get_set_status( size = PAGE_SIZE; /* initial guess */ for (;;) { - ipc_tree_entry_t tentry; - ipc_entry_t entry, table; - ipc_entry_num_t tsize; - mach_port_index_t index; + ipc_entry_t entry; mach_port_t *names; ipc_pset_t pset; @@ -986,11 +962,9 @@ mach_port_get_set_status( maxnames = size / sizeof(mach_port_t); actual = 0; - table = space->is_table; - tsize = space->is_table_size; - - for (index = 0; index < tsize; index++) { - ipc_entry_t ientry = &table[index]; + ipc_entry_t ientry; + struct rdxtree_iter iter; + rdxtree_for_each(&space->is_map, &iter, ientry) { ipc_entry_bits_t bits = ientry->ie_bits; if (bits & MACH_PORT_TYPE_RECEIVE) { @@ -1002,22 +976,6 @@ mach_port_get_set_status( } } - for (tentry = ipc_splay_traverse_start(&space->is_tree); - tentry != ITE_NULL; - tentry = ipc_splay_traverse_next(&space->is_tree,FALSE)) { - ipc_entry_bits_t bits = tentry->ite_bits; - - assert(IE_BITS_TYPE(bits) != MACH_PORT_TYPE_NONE); - - if (bits & MACH_PORT_TYPE_RECEIVE) { - ipc_port_t port = - (ipc_port_t) tentry->ite_object; - - mach_port_gst_helper(pset, port, maxnames, - names, &actual); - } - } - ipc_splay_traverse_finish(&space->is_tree); is_read_unlock(space); if (actual <= maxnames) -- cgit v1.2.3