diff options
author | Peter Zijlstra <peterz@infradead.org> | 2015-05-27 11:09:37 +0930 |
---|---|---|
committer | Rusty Russell <rusty@rustcorp.com.au> | 2015-05-28 11:32:07 +0930 |
commit | 93c2e105f6bcee231c951ba0e56e84505c4b0483 (patch) | |
tree | c81d9957d95194807d6907b1318047af16c71c5a /kernel/module.c | |
parent | ade3f510f93a5613b672febe88eff8ea7f1c63b7 (diff) | |
download | linux-stable-93c2e105f6bcee231c951ba0e56e84505c4b0483.tar.gz linux-stable-93c2e105f6bcee231c951ba0e56e84505c4b0483.tar.bz2 linux-stable-93c2e105f6bcee231c951ba0e56e84505c4b0483.zip |
module: Optimize __module_address() using a latched RB-tree
Currently __module_address() is using a linear search through all
modules in order to find the module corresponding to the provided
address. With a lot of modules this can take a lot of time.
One of the users of this is kernel_text_address() which is employed
in many stack unwinders; which in turn are used by perf-callchain and
ftrace (possibly from NMI context).
So by optimizing __module_address() we optimize many stack unwinders
which are used by both perf and tracing in performance sensitive code.
Cc: Rusty Russell <rusty@rustcorp.com.au>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Diffstat (limited to 'kernel/module.c')
-rw-r--r-- | kernel/module.c | 115 |
1 files changed, 110 insertions, 5 deletions
diff --git a/kernel/module.c b/kernel/module.c index a15899e00ca9..e0db5c31cb53 100644 --- a/kernel/module.c +++ b/kernel/module.c @@ -101,6 +101,108 @@ DEFINE_MUTEX(module_mutex); EXPORT_SYMBOL_GPL(module_mutex); static LIST_HEAD(modules); + +/* + * Use a latched RB-tree for __module_address(); this allows us to use + * RCU-sched lookups of the address from any context. + * + * Because modules have two address ranges: init and core, we need two + * latch_tree_nodes entries. Therefore we need the back-pointer from + * mod_tree_node. + * + * Because init ranges are short lived we mark them unlikely and have placed + * them outside the critical cacheline in struct module. + */ + +static __always_inline unsigned long __mod_tree_val(struct latch_tree_node *n) +{ + struct mod_tree_node *mtn = container_of(n, struct mod_tree_node, node); + struct module *mod = mtn->mod; + + if (unlikely(mtn == &mod->mtn_init)) + return (unsigned long)mod->module_init; + + return (unsigned long)mod->module_core; +} + +static __always_inline unsigned long __mod_tree_size(struct latch_tree_node *n) +{ + struct mod_tree_node *mtn = container_of(n, struct mod_tree_node, node); + struct module *mod = mtn->mod; + + if (unlikely(mtn == &mod->mtn_init)) + return (unsigned long)mod->init_size; + + return (unsigned long)mod->core_size; +} + +static __always_inline bool +mod_tree_less(struct latch_tree_node *a, struct latch_tree_node *b) +{ + return __mod_tree_val(a) < __mod_tree_val(b); +} + +static __always_inline int +mod_tree_comp(void *key, struct latch_tree_node *n) +{ + unsigned long val = (unsigned long)key; + unsigned long start, end; + + start = __mod_tree_val(n); + if (val < start) + return -1; + + end = start + __mod_tree_size(n); + if (val >= end) + return 1; + + return 0; +} + +static const struct latch_tree_ops mod_tree_ops = { + .less = mod_tree_less, + .comp = mod_tree_comp, +}; + +static struct latch_tree_root mod_tree __cacheline_aligned; + +/* + * These modifications: insert, remove_init and remove; are serialized by the + * module_mutex. + */ +static void mod_tree_insert(struct module *mod) +{ + mod->mtn_core.mod = mod; + mod->mtn_init.mod = mod; + + latch_tree_insert(&mod->mtn_core.node, &mod_tree, &mod_tree_ops); + if (mod->init_size) + latch_tree_insert(&mod->mtn_init.node, &mod_tree, &mod_tree_ops); +} + +static void mod_tree_remove_init(struct module *mod) +{ + if (mod->init_size) + latch_tree_erase(&mod->mtn_init.node, &mod_tree, &mod_tree_ops); +} + +static void mod_tree_remove(struct module *mod) +{ + latch_tree_erase(&mod->mtn_core.node, &mod_tree, &mod_tree_ops); + mod_tree_remove_init(mod); +} + +static struct module *mod_tree_find(unsigned long addr) +{ + struct latch_tree_node *ltn; + + ltn = latch_tree_find((void *)addr, &mod_tree, &mod_tree_ops); + if (!ltn) + return NULL; + + return container_of(ltn, struct mod_tree_node, node)->mod; +} + #ifdef CONFIG_KGDB_KDB struct list_head *kdb_modules = &modules; /* kdb needs the list of modules */ #endif /* CONFIG_KGDB_KDB */ @@ -1878,6 +1980,7 @@ static void free_module(struct module *mod) mutex_lock(&module_mutex); /* Unlink carefully: kallsyms could be walking list. */ list_del_rcu(&mod->list); + mod_tree_remove(mod); /* Remove this module from bug list, this uses list_del_rcu */ module_bug_cleanup(mod); /* Wait for RCU-sched synchronizing before releasing mod->list and buglist. */ @@ -3145,6 +3248,7 @@ static noinline int do_init_module(struct module *mod) mod->symtab = mod->core_symtab; mod->strtab = mod->core_strtab; #endif + mod_tree_remove_init(mod); unset_module_init_ro_nx(mod); module_arch_freeing_init(mod); mod->module_init = NULL; @@ -3215,6 +3319,7 @@ again: goto out; } list_add_rcu(&mod->list, &modules); + mod_tree_insert(mod); err = 0; out: @@ -3861,13 +3966,13 @@ struct module *__module_address(unsigned long addr) module_assert_mutex_or_preempt(); - list_for_each_entry_rcu(mod, &modules, list) { + mod = mod_tree_find(addr); + if (mod) { + BUG_ON(!within_module(addr, mod)); if (mod->state == MODULE_STATE_UNFORMED) - continue; - if (within_module(addr, mod)) - return mod; + mod = NULL; } - return NULL; + return mod; } EXPORT_SYMBOL_GPL(__module_address); |