[PATCH] modules: Take a shortcut for checking if an address is in a module

[PATCH] modules: Take a shortcut for checking if an address is in a module

[Arjan van de Ven]

From: Arjan van de Ven <arjan@linux.intel.com>
Subject: [PATCH] modules: Take a shortcut for checking if an address is in a module

Various pieces of the kernel (lockdep, latencytop, etc) tend to store
backtraces, sometimes at a relatively high frequency. In itself this
isn't a big performance deal (after all you're using diagnostics features),
but there have been some complaints from people who have over 100 modules
loaded that this is a tad too slow.

This is due to the new backtracer code which looks at every slot on the stack
to see if it's a kernel/module text address, so that's 1024 slots.
1024 times 100 modules... that's a lot of list walking.

On some architectures (esp x86), the modules go into a specific range of
virtual memory; this patch adds a check just before walking the module
list to see if the address that's asked for is in the module range in
the first place, and manages to skip the list walk for the (common) case
of this not being so.


Signed-off-by: Arjan van de Ven <arjan@linux.intel.com>
---
 kernel/module.c |   15 +++++++++++++++
 1 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
index 5f80478..b7dbef1 100644
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -2595,6 +2595,21 @@ struct module *__module_text_address(unsigned long addr)
 {
 	struct module *mod;
 
+	/* 
+	 * shortcut for the architectures that have a well
+	 * defined start/end virtual address of modules:
+	 * we can decide something for sure isn't a module
+	 * without walking the potentially long module list.
+	 */
+#ifdef MODULES_VADDR
+	if (addr < MODULES_VADDR)
+		return NULL;
+#endif
+#ifdef MODULES_END
+	if (addr > MODULES_END)
+		return NULL;
+#endif
+
 	list_for_each_entry(mod, &modules, list)
 		if (within(addr, mod->module_init, mod->init_text_size)
 		    || within(addr, mod->module_core, mod->core_text_size))
-- 
1.5.4.5


-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Rusty Russell]

On Wednesday 11 June 2008 06:05:19 Arjan van de Ven wrote:
> From: Arjan van de Ven <arjan@linux.intel.com>
> Subject: [PATCH] modules: Take a shortcut for checking if an address is in
> a module
>
> Various pieces of the kernel (lockdep, latencytop, etc) tend to store
> backtraces, sometimes at a relatively high frequency. In itself this
> isn't a big performance deal (after all you're using diagnostics features),
> but there have been some complaints from people who have over 100 modules
> loaded that this is a tad too slow.

Nothing wrong with the idea, but how about a nice arch_maybe_module_addr() 
macro rather than ifdefs in module.c?

Thanks,
Rusty.

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Arjan van de Ven]

On Wed, 11 Jun 2008 21:12:08 +1000
Rusty Russell <rusty@rustcorp.com.au> wrote:

> On Wednesday 11 June 2008 06:05:19 Arjan van de Ven wrote:
> > From: Arjan van de Ven <arjan@linux.intel.com>
> > Subject: [PATCH] modules: Take a shortcut for checking if an
> > address is in a module
> >
> > Various pieces of the kernel (lockdep, latencytop, etc) tend to
> > store backtraces, sometimes at a relatively high frequency. In
> > itself this isn't a big performance deal (after all you're using
> > diagnostics features), but there have been some complaints from
> > people who have over 100 modules loaded that this is a tad too slow.
> 
> Nothing wrong with the idea, but how about a nice
> arch_maybe_module_addr() macro rather than ifdefs in module.c?

Everytime someone says that, I go crawl under my desk and weep quietly
for 10 minutes.

Yes ifdefs aren't nice. However, arch_foo_bar_baz() is equally bad, it
just moves the uglyness around a little. It's like multiplying the dirt
by three and then sweeping it under 3 different carpets. Sure in your
area the room looks clean, but the total amount of crap didn't decrease.

The only half-way sane way to do arch_has_foo is using weak functions,
but unfortunately that runs into gcc issues to the point of not being
usable without a great amount of care... the alternatives are both
unpleasant and overkill. We really should try to keep the arch stuff as
small as possible; a gazillion arch_foo_bar()'s is the opposite
direction there ;(


-- 
If you want to reach me at my work email, use arjan@linux.intel.com
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Vegard Nossum]

On 6/11/08, Arjan van de Ven <arjan@infradead.org> wrote:
> On Wed, 11 Jun 2008 21:12:08 +1000
>  Rusty Russell <rusty@rustcorp.com.au> wrote:
>
>  > On Wednesday 11 June 2008 06:05:19 Arjan van de Ven wrote:
>  > > From: Arjan van de Ven <arjan@linux.intel.com>
>  > > Subject: [PATCH] modules: Take a shortcut for checking if an
>  > > address is in a module
>  > >
>  > > Various pieces of the kernel (lockdep, latencytop, etc) tend to
>  > > store backtraces, sometimes at a relatively high frequency. In
>  > > itself this isn't a big performance deal (after all you're using
>  > > diagnostics features), but there have been some complaints from
>  > > people who have over 100 modules loaded that this is a tad too slow.

Would it be overkill to simply drop the module addresses in an rbtree
and use that instead of a linear search over all the modules?

It would probably take a fair number of lines in C, and with a little
memory overhead, but the speed-up should be great. Should I give it a
try? (It would be arch-independent too.)


Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Ingo Molnar]

* Vegard Nossum <vegard.nossum@gmail.com> wrote:

> >  > > Various pieces of the kernel (lockdep, latencytop, etc) tend to 
> >  > > store backtraces, sometimes at a relatively high frequency. In 
> >  > > itself this isn't a big performance deal (after all you're 
> >  > > using diagnostics features), but there have been some 
> >  > > complaints from people who have over 100 modules loaded that 
> >  > > this is a tad too slow.
> 
> Would it be overkill to simply drop the module addresses in an rbtree 
> and use that instead of a linear search over all the modules?
> 
> It would probably take a fair number of lines in C, and with a little 
> memory overhead, but the speed-up should be great. Should I give it a 
> try? (It would be arch-independent too.)

that's a tempting idea. rbtrees seem to be equally robust to plain lists 
in my experience, so i'd not find the extra complexity a showstopper, as 
long as the changes are well-tested. (radix trees on the other hand ... 
;-)

Rusty, Peter, Linus, any fundamental objections to Vegard's idea? Being 
able to take a transparent stack-trace signature for debugging or 
instrumentation purposes is important and performance does matter there 
IMO.

	Ingo

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Peter Zijlstra]

On Wed, 2008-06-18 at 11:57 +0200, Ingo Molnar wrote:
> * Vegard Nossum <vegard.nossum@gmail.com> wrote:
> 
> > >  > > Various pieces of the kernel (lockdep, latencytop, etc) tend to 
> > >  > > store backtraces, sometimes at a relatively high frequency. In 
> > >  > > itself this isn't a big performance deal (after all you're 
> > >  > > using diagnostics features), but there have been some 
> > >  > > complaints from people who have over 100 modules loaded that 
> > >  > > this is a tad too slow.
> > 
> > Would it be overkill to simply drop the module addresses in an rbtree 
> > and use that instead of a linear search over all the modules?
> > 
> > It would probably take a fair number of lines in C, and with a little 
> > memory overhead, but the speed-up should be great. Should I give it a 
> > try? (It would be arch-independent too.)
> 
> that's a tempting idea. rbtrees seem to be equally robust to plain lists 
> in my experience, so i'd not find the extra complexity a showstopper, as 
> long as the changes are well-tested. (radix trees on the other hand ... 
> ;-)

Radix trees are unsuited for this application, esp in their current
implementation.

> Rusty, Peter, Linus, any fundamental objections to Vegard's idea? Being 
> able to take a transparent stack-trace signature for debugging or 
> instrumentation purposes is important and performance does matter there 
> IMO.

A tree makes sense, although if more archs can do the same Arjan did for
x86 that'd be even better.

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Rusty Russell]

On Wednesday 18 June 2008 20:24:31 Peter Zijlstra wrote:
> On Wed, 2008-06-18 at 11:57 +0200, Ingo Molnar wrote:
> > * Vegard Nossum <vegard.nossum@gmail.com> wrote:
> > > Would it be overkill to simply drop the module addresses in an rbtree
> > > and use that instead of a linear search over all the modules?
> >
> > that's a tempting idea. rbtrees seem to be equally robust to plain lists
> > in my experience, so i'd not find the extra complexity a showstopper, as
> > long as the changes are well-tested. (radix trees on the other hand ...
> > ;-)
>
> Radix trees are unsuited for this application, esp in their current
> implementation.
>
> > Rusty, Peter, Linus, any fundamental objections to Vegard's idea? Being
> > able to take a transparent stack-trace signature for debugging or
> > instrumentation purposes is important and performance does matter there
> > IMO.
>
> A tree makes sense, although if more archs can do the same Arjan did for
> x86 that'd be even better.

Please, just track the max and min module addresses at run time.  That's 
simple, arch-indep and even offers slightly better performance than 
Arjan's :)

Cheers,
Rusty.

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Rusty Russell]

On Thursday 12 June 2008 01:18:47 Arjan van de Ven wrote:
> On Wed, 11 Jun 2008 21:12:08 +1000
>
> Rusty Russell <rusty@rustcorp.com.au> wrote:
> > On Wednesday 11 June 2008 06:05:19 Arjan van de Ven wrote:
> > > From: Arjan van de Ven <arjan@linux.intel.com>
> > > Subject: [PATCH] modules: Take a shortcut for checking if an
> > > address is in a module
> > >
> > > Various pieces of the kernel (lockdep, latencytop, etc) tend to
> > > store backtraces, sometimes at a relatively high frequency. In
> > > itself this isn't a big performance deal (after all you're using
> > > diagnostics features), but there have been some complaints from
> > > people who have over 100 modules loaded that this is a tad too slow.
> >
> > Nothing wrong with the idea, but how about a nice
> > arch_maybe_module_addr() macro rather than ifdefs in module.c?
>
> Everytime someone says that, I go crawl under my desk and weep quietly
> for 10 minutes.
>
> Yes ifdefs aren't nice. However, arch_foo_bar_baz() is equally bad, it
> just moves the uglyness around a little. It's like multiplying the dirt
> by three and then sweeping it under 3 different carpets. Sure in your
> area the room looks clean, but the total amount of crap didn't decrease.
>
> The only half-way sane way to do arch_has_foo is using weak functions,
> but unfortunately that runs into gcc issues to the point of not being
> usable without a great amount of care... the alternatives are both
> unpleasant and overkill. We really should try to keep the arch stuff as
> small as possible; a gazillion arch_foo_bar()'s is the opposite
> direction there ;(

OK, then how about something like this in linux/module.h:

#ifndef MODULE_ADDR_MIN
#define MODULE_ADDR_MIN OUL
#endif
#ifndef MODULE_ADDR_MAX
#define MODULE_ADDR_MAX -1UL
#endif

Or, we could actually make those as variables and update them in module.c 
itself.  No arch changes required, and pretty easy to understand.

Cheers,
Rusty.

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Rusty Russell]

On Thursday 12 June 2008 10:20:58 Rusty Russell wrote:
> Or, we could actually make those as variables and update them in module.c
> itself.  No arch changes required, and pretty easy to understand.

And since you didn't reply, here's the patch.

modules: Take a shortcut for checking if an address is in a module

This patch keeps track of the boundaries of module allocation, in
order to speed up module_text_address().

Inspired by Arjan's version, which required arch-specific defines:

	Various pieces of the kernel (lockdep, latencytop, etc) tend
	to store backtraces, sometimes at a relatively high
	frequency. In itself this isn't a big performance deal (after
	all you're using diagnostics features), but there have been
	some complaints from people who have over 100 modules loaded
	that this is a tad too slow.

	This is due to the new backtracer code which looks at every
	slot on the stack to see if it's a kernel/module text address,
	so that's 1024 slots.  1024 times 100 modules... that's a lot
	of list walking.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
---
 kernel/module.c |   24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

diff --git a/kernel/module.c b/kernel/module.c
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -69,6 +69,9 @@ static DECLARE_WAIT_QUEUE_HEAD(module_wq
 static DECLARE_WAIT_QUEUE_HEAD(module_wq);
 
 static BLOCKING_NOTIFIER_HEAD(module_notify_list);
+
+/* Bounds of module allocation, for speeding __module_text_address */
+static unsigned long module_addr_min = -1UL, module_addr_max = 0;
 
 int register_module_notifier(struct notifier_block * nb)
 {
@@ -1770,6 +1773,20 @@ static inline void add_kallsyms(struct m
 }
 #endif /* CONFIG_KALLSYMS */
 
+static void *module_alloc_update_bounds(unsigned long size)
+{
+	void *ret = module_alloc(size);
+
+	if (ret) {
+		/* Update module bounds. */
+		if ((unsigned long)ret < module_addr_min)
+			module_addr_min = (unsigned long)ret;
+		if ((unsigned long)ret + size > module_addr_max)
+			module_addr_max = (unsigned long)ret + size;
+	}
+	return ret;
+}
+
 /* Allocate and load the module: note that size of section 0 is always
    zero, and we rely on this for optional sections. */
 static struct module *load_module(void __user *umod,
@@ -1971,7 +1988,7 @@ static struct module *load_module(void _
 	layout_sections(mod, hdr, sechdrs, secstrings);
 
 	/* Do the allocs. */
-	ptr = module_alloc(mod->core_size);
+	ptr = module_alloc_update_bounds(mod->core_size);
 	if (!ptr) {
 		err = -ENOMEM;
 		goto free_percpu;
@@ -1979,7 +1996,7 @@ static struct module *load_module(void _
 	memset(ptr, 0, mod->core_size);
 	mod->module_core = ptr;
 
-	ptr = module_alloc(mod->init_size);
+	ptr = module_alloc_update_bounds(mod->init_size);
 	if (!ptr && mod->init_size) {
 		err = -ENOMEM;
 		goto free_core;
@@ -2636,6 +2653,9 @@ struct module *__module_text_address(uns
 {
 	struct module *mod;
 
+	if (addr < module_addr_min || addr > module_addr_max)
+		return NULL;
+
 	list_for_each_entry(mod, &modules, list)
 		if (within(addr, mod->module_init, mod->init_text_size)
 		    || within(addr, mod->module_core, mod->core_text_size))

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Ingo Molnar]

* Rusty Russell <rusty@rustcorp.com.au> wrote:

> On Thursday 12 June 2008 10:20:58 Rusty Russell wrote:
> > Or, we could actually make those as variables and update them in module.c
> > itself.  No arch changes required, and pretty easy to understand.
> 
> And since you didn't reply, here's the patch.
> 
> modules: Take a shortcut for checking if an address is in a module
> 
> This patch keeps track of the boundaries of module allocation, in
> order to speed up module_text_address().
> 
> Inspired by Arjan's version, which required arch-specific defines:

great - i've also put this into tip/out-of-tree for more testing.

	Ingo

Re: [PATCH] modules: Take a shortcut for checking if an address is in a module

[Ingo Molnar]

* Arjan van de Ven <arjan@infradead.org> wrote:

> > Nothing wrong with the idea, but how about a nice 
> > arch_maybe_module_addr() macro rather than ifdefs in module.c?
> 
> Everytime someone says that, I go crawl under my desk and weep quietly 
> for 10 minutes.

i've added your patch for testing purposes to tip/out-of-tree.

(An updated patch with the module.h change suggested by Rusty, as long 
as acked by Rusty could go into tip/core/locking and thus show up in 
linux-next as well.)

	Ingo