[SCM] GNU Mach branch, master, updated. v1.5-23-g4934e7c

[Justus Winter]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU Mach".

The branch, master has been updated
       via  4934e7c3735dbd25953c922a1327a875f47046a4 (commit)
       via  77b3b60aaee2382142dc7ed50e5b36664cdb21bc (commit)
       via  5a00790518773385e681e6430a4f85245fae957d (commit)
       via  aac601ac36c623247a51d442b2d6438b042d7515 (commit)
       via  7d76ea075c248b2ed64c69a5e5dd4493d943e628 (commit)
      from  6eb79f812ee43a4e9142de61a5821e0cc8c52bb1 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit 4934e7c3735dbd25953c922a1327a875f47046a4
Author: Justus Winter <address@hidden>
Date:   Wed Apr 1 17:17:01 2015 +0200

    ipc: inline key ipc entry lookup functions
    
    Declare functions looking up IPC entries that were previously inlined
    manually with `static inline' so that they will be inlined into the
    fast paths by the compiler.
    
    * ipc/ipc_entry.c (ipc_entry_lookup, ipc_entry_get,
    ipc_entry_dealloc): Move functions...
    * ipc/ipc_space.h: ... here, and declare them as `static inline'.
    * ipc/ipc_entry.h: Drop associated declarations.

commit 77b3b60aaee2382142dc7ed50e5b36664cdb21bc
Author: Justus Winter <address@hidden>
Date:   Fri Mar 20 00:21:14 2015 +0100

    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.

commit 5a00790518773385e681e6430a4f85245fae957d
Author: Justus Winter <address@hidden>
Date:   Wed Mar 18 12:25:26 2015 +0100

    ipc: replace reverse hash table with a radix tree
    
    Currently, there is a hash table mapping (space, object) tuples to
    `ipc_entry' objects.  This hash table is intertwined with the IPC
    tables.  There is one hash table per IPC space, but it is only for the
    entries in the IPC table.  This hash table is called `local' in the
    source.  All IPC entries being spilled into the splay tree are instead
    mapped by a global hash table.
    
    Replace the local (i.e. per IPC space) reverse hash table with a radix
    tree.
    
    * ipc/ipc_entry.c (ipc_entry_grow_table): Adjust accordingly.
    * ipc/ipc_entry.h (struct ipc_entry): Adjust comment.
    * ipc/ipc_hash.c: Adjust comment explaining the local lookup table.
    (IPC_LOCAL_HASH_INVARIANT): New macro.
    (ipc_hash_local_lookup): Use the new `ipc_reverse_lookup' function.
    (ipc_hash_local_insert): Use the new `ipc_reverse_insert' function.
    (ipc_hash_local_delete): Use the new `ipc_reverse_remove' function.
    * ipc/ipc_space.c (ipc_space_create): Initialize radix tree.
    (ipc_space_destroy): Free radix tree.
    * ipc/ipc_space.h (struct ipc_space): Add radix tree.
    (ipc_reverse_insert): New function.
    (ipc_reverse_remove): Likewise.
    (ipc_reverse_remove_all): Likewise.
    (ipc_reverse_lookup): Likewise.
    * ipc/ipc_right.c (ipc_right_clean): Update comment.

commit aac601ac36c623247a51d442b2d6438b042d7515
Author: Justus Winter <address@hidden>
Date:   Mon Mar 16 12:52:24 2015 +0100

    ipc: undo manual inlining of `ipc_entry_X' functions
    
    Today we can rely on the compiler to inline functions.  Undoing this
    manual optimization is a first step to replace the IPC tables.
    
    * ipc/mach_msg.c (mach_msg_trap): Undo the manual inlining of
    `ipc_entry_lookup', `ipc_entry_dealloc', and `ipc_entry_get'.
    * ipc/ipc_kmsg.c (ipc_kmsg_copyin_header, ipc_kmsg_copyout_header): 
Likewise.
    * kern/exception.c (exception_raise): Likewise.
    * kern/ipc_mig.c (fast_send_right_lookup): Likewise.

commit 7d76ea075c248b2ed64c69a5e5dd4493d943e628
Author: Justus Winter <address@hidden>
Date:   Mon Mar 16 11:37:06 2015 +0100

    kern: add radix tree library
    
    Import a radix tree library from Richard Braun's librbraun.
    
    * Makefile.am (clib_routines): Steal `__ffsdi2'.
    * Makefrag.am (libkernel_a_SOURCES): Add new files.
    * kern/rdxtree.c: New file.
    * kern/rdxtree.h: Likewise.
    * kern/rdxtree_i.h: Likewise.
    * kern/startup.c (setup_main): Initialize radix tree library.

-----------------------------------------------------------------------

Summary of changes:
 Makefile.am                              |    1 +
 Makefrag.am                              |    7 +-
 ddb/db_print.c                           |   20 +-
 include/mach_debug/ipc_info.h            |   23 -
 include/mach_debug/mach_debug.defs       |   21 +-
 include/mach_debug/mach_debug_types.defs |    7 +-
 ipc/ipc_entry.c                          |  790 +++-----------------------
 ipc/ipc_entry.h                          |   69 +--
 ipc/ipc_hash.c                           |  620 --------------------
 ipc/ipc_hash.h                           |   96 ---
 ipc/ipc_init.c                           |    6 +-
 ipc/ipc_kmsg.c                           |  137 ++----
 ipc/ipc_object.c                         |   23 +-
 ipc/ipc_right.c                          |   41 +-
 ipc/ipc_space.c                          |  103 +---
 ipc/ipc_space.h                          |  199 ++++++-
 ipc/ipc_splay.c                          |  920 ------------------------------
 ipc/ipc_splay.h                          |  114 ----
 ipc/mach_debug.c                         |  325 -----------
 ipc/mach_msg.c                           |  139 +----
 ipc/mach_port.c                          |   60 +--
 ipc/port.h                               |    5 +-
 kern/exception.c                         |   18 +-
 kern/ipc_mig.c                           |   14 +-
 kern/rdxtree.c                           |  830 +++++++++++++++++++++++++++
 kern/rdxtree.h                           |  209 +++++++
 kern/rdxtree_i.h                         |   66 +++
 kern/startup.c                           |    2 +
 28 files changed, 1524 insertions(+), 3341 deletions(-)
 delete mode 100644 ipc/ipc_hash.c
 delete mode 100644 ipc/ipc_hash.h
 delete mode 100644 ipc/ipc_splay.c
 delete mode 100644 ipc/ipc_splay.h
 create mode 100644 kern/rdxtree.c
 create mode 100644 kern/rdxtree.h
 create mode 100644 kern/rdxtree_i.h


hooks/post-receive
-- 
GNU Mach