summaryrefslogtreecommitdiff
path: root/ipc/ipc_splay.h
AgeCommit message (Collapse)Author
2015-05-20ipc: replace the IPC table with a radix treeJustus Winter
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.
2015-05-19kern: import `macros.h' from x15Justus Winter
Import the macro definitions from the x15 kernel project, and replace all similar definitions littered all over the place with it. Importing this file will make importing code from the x15 kernel easier. We are already using the red-black tree implementation and the slab allocator from it, and we will import even more code in the near future. * kern/list.h: Do not define `structof', include `macros.h' instead. * kern/rbtree.h: Likewise. * kern/slab.c: Do not define `ARRAY_SIZE', include `macros.h' instead. * i386/grub/misc.h: Likewise. * i386/i386/xen.h: Do not define `barrier', include `macros.h' instead. * kern/macro_help.h: Delete file. Replaced by `macros.h'. * kern/macros.h: New file. * Makefrag.am (libkernel_a_SOURCES): Add new file, remove old file. * device/dev_master.h: Adopt accordingly. * device/io_req.h: Likewise. * device/net_io.h: Likewise. * i386/intel/read_fault.c: Likewise. * ipc/ipc_kmsg.h: Likewise. * ipc/ipc_mqueue.h: Likewise. * ipc/ipc_object.h: Likewise. * ipc/ipc_port.h: Likewise. * ipc/ipc_space.h: Likewise. * ipc/ipc_splay.c: Likewise. * ipc/ipc_splay.h: Likewise. * kern/assert.h: Likewise. * kern/ast.h: Likewise. * kern/pc_sample.h: Likewise. * kern/refcount.h: Likewise. * kern/sched.h: Likewise. * kern/sched_prim.c: Likewise. * kern/timer.c: Likewise. * kern/timer.h: Likewise. * vm/vm_fault.c: Likewise. * vm/vm_map.h: Likewise. * vm/vm_object.h: Likewise. * vm/vm_page.h: Likewise.
1997-02-25Initial sourceThomas Bushnell